代码的时间复杂度或大O

Question

我有一个最大堆属性的数组。 deleteMax 的时间复杂度为 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)

哪一个是正确的？

Answer 1

如果循环只有运行s 7次那么复杂度是O(1)。这是因为循环不依赖于数据的大小，并且在恒定时间内总是运行。

Answer 2

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

Answer 3

我想你是在学习堆排序算法，我确定复杂度是 O(nlogn)。

Answer 4

一般来说，当一个数字是固定的（又名常量）时谈论复杂性是没有意义的。该符号的全部目的是评估执行时间在数字变化时如何变化。恒定数量的循环永远不会改变执行时间和复杂性。如果将循环次数更改为 另一个 常数值，它将改变执行时间但复杂度是相同的。

典型用途是计算函数的复杂性，以便让函数的用户了解当用户更改某些输入值时执行时间如何变化。示例：

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)。仅仅是因为没有输入改变循环次数。

代码的时间复杂度或大O

Time complexity or Big O of the code

c

heap

time-complexity

binary-heap

data-structures