big-o - 对初学者的大帮助

Question

好的，我正在尝试理解大 O 的概念。我有一个功能，我想找到大 O，但我不是很“明白”，这是书中的一个例子，就像我的家庭作业一样。我知道答案是 O(nk)，但有人可以用简单的术语把它分解一下，这样我可能会更好地理解。

int selectkth(int a[], int k, int n)
{
int i, j, mini, tmp;
for (i=0; i < k; i++)
{
mini = i;
for (j = i+1; j < n; j++)
{
if (a[j] < a[mini])
mini = k;
tmp = a[i];
a[i] = a[mini];
a[mini] = tmp;
}
}
return a[k-1];
}

Answer 1

在计算 bigO 时，尽量考虑最坏的时间复杂度，并注意循环。这里我们有两个循环：

// 下面的行运行 k 次

对于 (i=0; i < k; i++)

// 最坏的情况，下面的循环将运行 n 次。

对于 (j = i+1; j < n; j++)

bigO 将是这两个值的乘积 = k*n

另请查看这篇文章：“Big O”符号的简单英文解释是什么？