代码的时间复杂度或大O表示法

Question

我有一个数组，它具有最大堆的特性。删除最大值的时间复杂度是O(logn)。如果下面的代码只迭代7次，那么下面的代码时间复杂度是多少（大O）？

int heap_size = 15;
int i, value, heap_array[]; // array is in the form of max heap
....
for(i = 0; i < 7; i++){ // iterates seven times
    value = deleteMax(heap_array);
    printf("%d ", value);
}

我有两个解决方案。第一个：时间复杂度为O(7 * logn)或简单地说是O(logn)。

然后第二个解决方案是O(1/2 * n * logn)或O(nlogn)，因为1/2只是一个常数，而且我假设迭代次数为7，几乎与heap_size的一半相同，因此可以忽略1/2。因此是O(nlogn)。

哪一个正确呢？

- labyrinthdeux

---

如果堆大小始终为15，则此处具有恒定的时间复杂度。O(1)。这不是输入的函数，因为没有输入。 - xiaofeng.li

@LukeLee 我认为你需要考虑在 for 循环内部的 deleteMax 函数——O(logn)，以及 for 循环中的迭代次数？我感到困惑的是，for 循环仅迭代至 7 个元素而不是整个 heap_size。 - labyrinthdeux

你选了一个不好的例子。如果for循环运行了n/2次，那就更有趣了。 - xiaofeng.li

这可能就是你实际所要求的。 - xiaofeng.li

Answer 1

通常情况下，当一个数字是固定的（也称为常数）时，谈论复杂性是没有意义的。符号的全部目的是评估执行时间在数字变化时如何改变。恒定数量的循环永远不会改变执行时间或复杂度。如果您将循环次数更改为另一个常数值，则会更改执行时间但复杂度保持不变。

典型用途是计算函数复杂度，以便为函数用户提供一种当用户更改某些输入值时，执行时间如何改变的想法。例如：

void foo()                 // Pointless to talk about complexity as there is no input

void foo(int x)            // Complexity tells you how execution time change 
                           // when you change x

void foo(char* someString) // Complexity tells you how execution time change 
                           // when you change the length of someString

注意：复杂度从不告诉你实际执行时间！只有在某些输入发生改变时才会告诉你执行时间的变化。

因此，在您的情况下，仍然是“deleteMax”确定了复杂度，即它仍然是O(log n)。只是因为没有任何输入改变循环次数。

- Support Ukraine

---

所以，如果我将i < 7更改为i < 20（假设这是无误的），时间复杂度仍然是O(logn)，因为它不依赖于数据的大小？我的理解正确吗？顺便说一下，答案已被接受。谢谢。 - labyrinthdeux

@labyrinthdeux 正确。从7改为20不会影响复杂度。这种符号不是用来表示执行代码所需的时间。这种符号告诉你当你改变某些东西时，比如输入数组的长度时，执行时间会如何改变。 - Support Ukraine

@labyrinthdeux - 但是如果您让循环限制取决于某些输入值，例如 i < someInputValue，那么复杂性将会改变。 - Support Ukraine

@4386427：我想补充一下，复杂度告诉你当某些输入改变时执行时间如何变化，_对于大规模的输入而言_。这是因为我们只保留主导项。如果执行时间由T(n) = n^2 + 1000*n给出，则复杂度为O(n^2)，但对于小的n，增长将接近线性。只有对于更大的n，它才会变成（接近）二次方。 - Thomas Padron-McCarthy

Answer 2

如果循环只运行7次，则复杂度为O(1)。这是因为循环不依赖于数据的大小，始终以恒定时间运行。

- Archmede

---

那么，如果我将i < 7更改为i < 20（假设这是无错误的），时间复杂度仍将是O（logn），因为它不依赖于数据大小？这个理解正确吗？ - labyrinthdeux

@Archmede：如果循环运行固定次数，则复杂度将与deleteMax相同，后者被说明为O(log n)。 - Thomas Padron-McCarthy

Answer 3

在这里，堆大小和循环运行次数都是恒定的。因此，代码的时间复杂度为O(1)，即恒定时间复杂度。

- vantony

Answer 4

我认为你正在学习堆排序算法，我确定它的复杂度是O(nlogn)。

- slzy