algorithm - 时间复杂度(关于 n 输入)

Question

我被问到如果这样的话时间复杂度是多少:

这个算法的时间复杂度(关于 n)是多少:

k=0
for(i = n / 2 ; i < n ; i++ ) {
   for( j=0 ; j < i ; j++)
      k = k + n / 2
}

选择是:a。 O(n) b。 O(n/2) c. O(n log(n) 和 d.O(n^2)

可以有多个答案。

我知道上面的算法是d。 O(n^2) 但我是用 a 来的。 O(n) 因为它只寻找 n 的复杂度？

如果你有这个问题。你会怎么回答呢？？我很好奇答案。

Answer 1

答案是 O(n²)。

这个很容易理解。我会尽力让你理解它。

看，外面for循环 block 被执行n - n/2 = n/2次。

当然要看是不是数字n是偶数还是奇数。如果是偶数，则执行外循环 n/2次。如果是奇数，则执行 (n-1)/2次。

但是对于时间复杂度，我们不考虑这个。我们只是假设外层 for循环被执行n/2时代i从 n/2 开始结束于 n - 1 (因为终止条件是 i < n 而不是 i <= n )。

对于外循环的每次迭代，内循环执行i次。

例如，对于每次迭代，内部循环都以 j = 0 开始至 j = i - 1 .这意味着它执行 i次(不是 i - 1 次，因为 j 从 0 而不是 1 开始)。

因此，对于第 1 次迭代，执行内部循环 i = n / 2次。 i = n / 2 + 1第二次迭代等等直到i = n - 1次。

现在，总数没有。内部循环执行的次数是 n/2 + (n/2 + 1) + (n/2 + 2) + ... + (n - 2) + (n - 1) .这是一个简单的数学，总结为 (3n² - n)/2次。

因此，时间复杂度变为 O((3n² - n)/2)。

但是我们忽略了n术语因为n² > n和常数项，因为对于每个 n它们将保持不变。

因此，最终的时间复杂度为O(n²)。

希望这能帮助你理解。