c++ - 用 Big-O Notation 计算我的程序的算法复杂度

Question

我创建了这个程序，它将对用户输入的订单列表进行二进制搜索，并输出他们想要在该列表中搜索的所需值。我的问题是我必须为我的代码的每个部分找到 Big-O Notation 中的算法复杂度，然后计算它的时间复杂度，但是，我并不擅长弄清楚 Big-O 表示法。如果可能的话，你能解释一下我是怎么做到的等等。这是我的代码，我已经尝试计算出某些行的算法复杂性，如果我做错了什么，请纠正我。

#include<iostream>
#include<vector>
using namespace std;


int binarySearch(vector<double> uservector, int, int);


int main()
{
int size;  // O(1)
int i;  //O(1)
int desirednum;  // O(1)

cout << "How many values do you want to enter: ";  // O(1)
cin >> size;  // O(1)
vector<double> uservector(size);

for (i = 0; i < size; i++)
{
    cout << "Enter a value: ";
    cin >> uservector[i];
}

cout << "What value are you looking for: ";  // O(1)
cin >> desirednum;  // O(1)

int location = binarySearch(uservector, size, desirednum);  

if( location > -1)
    cout << "The value " << desirednum << " was found at index " << location   << endl;  // O(1)
else 
    cout << "The value was not found in the list. \n";  // O(1)

system("PAUSE");
return 0;
}

int binarySearch(vector<double> uservector, int size, int value)
{
int low, mid, high;

low = 0;
high = size - 1;
while(low <= high)
{
    mid = ((low + high) / 2);
    if(value == uservector[mid])
    {
        return
            mid;
    }
    else if(value > uservector[mid])
        low = mid + 1;
    else
        high = mid - 1;
}
    return -1;
}

Answer 1

在某种程度上，您是对的。对其他人来说，你不知道。

int main()
{
int size;  // O(1)
int i;  //O(1)
int desirednum;  // O(1)

这些不是说明，而是声明。它们根本不需要运行时间。

cout << "How many values do you want to enter: ";  // O(1)

您根本不应该对算法开始之前发生的事情进行计数。

cin >> size;  // O(1)
vector<double> uservector(size);

for (i = 0; i < size; i++)
{
    cout << "Enter a value: ";
    cin >> uservector[i];
}

cout << "What value are you looking for: ";  // O(1)
cin >> desirednum;  // O(1)

您根本不应该对算法开始之前发生的事情进行计数。

int location = binarySearch(uservector, size, desirednum);  

if( location > -1)
    cout << "The value " << desirednum << " was found at index " << location   << endl;  // O(1)
else 
    cout << "The value was not found in the list. \n";  // O(1)

system("PAUSE");
return 0;
}

好的，现在开始你真正想要复杂的部分。

int binarySearch(vector<double> uservector, int size, int value)
{
int low, mid, high;

low = 0;
high = size - 1;
while(low <= high)
{
    mid = ((low + high) / 2);
    if(value == uservector[mid])
    {
        return
            mid;
    }
    else if(value > uservector[mid])
        low = mid + 1;
    else
        high = mid - 1;
}
    return -1;
}

您每次迭代都将到目标的距离减半，从而使您的复杂度达到 log2(N)。