algorithm - 此特定 For 循环的运行时间

Question

我正在研究一个算法问题，想检验我对这一特定行的运行时间的直觉:

for i= floor(A.heapsize/2)+1 to A.heapsize //iterate through leaves of heap

其中 A.heap-size 与 n 相同，for 循环中的其他所有内容都需要常数时间。循环是否在 O(n) 时间内运行？

Answer 1

是的，它是 O(n)。常数因子从大 O 表示法中删除，无论它是大于一还是小于一。在您的例子中，常数因子是 ½。