基本算法分析和 While 循环行为

Question

"Analyze the pseudocode below and give the asymptotic worst-case running time of each function as a Big-Theta expression."

我已经包含了下面的代码，并注释了每一行的操作计数。这道题使用了一个假设的架构，其中每个原始操作需要 1 个时间单位。

1: procedure KSum1(n)
2:     S ← 0 // 1 for assignment
3:     k ← n // 1 for assignment
4:     while k ≥ 1 do // THIS IS THE PROBLEM
5:         for i = 1, 2, . . . , k do // n*(whatever the while loop is)
6:             S ← S + k // (1 for add + 1 for assignment)*(whatever the while loop is)
7:         end for
8:         k ← k/2  // (1 for divide + 1 for assignment)*(whatever the while loop is)
9:     end while
10:     return S // 1
11: end procedure

如您所见，我不确定在这种情况下如何处理 while 循环。

如果n = 4，则循环4→2→1，所以3加上额外的检查，总共4。

如果n=7，则循环7→3.5→1.75，3加1共4

若n=9，则循环为9→4.5→2.25→1.125，4加1共5

等等

我很难想出一种模式来将 while 循环的重复次数表示为 n 的函数，这使我无法完成此问题。谁能指出我正确的方向？算法分析新手，如有任何帮助，我们将不胜感激！

Answer 1

时间复杂度将为 O(log(n))，这意味着对于给定的 n，将需要 log(n) 步来计算算法（或更正式地说：算法的顺序表示给定问题的函数是 log(n)).

您已完成此分析中的大部分工作：

If n = 4, then it loops 4→2→1, so 3 plus an extra check for a total of 4.

If n = 7, then it loops 7→3.5→1.75, 3 plus 1 for a total of 4.

If n = 9, the loop is 9→4.5→2.25→1.125, 4 plus 1 for a total of 5.

此处的“步骤”由一个右箭头表示，因此对于 4 和 7 有 2 个步骤，对于 9 有 3 个步骤。让我们将其与 floor(log(n)):

进行比较

`n = 4, log_2(4) = 2,             floor(log_2(4)) = 2, #arrows = 2`
`n = 7, log_2(7) = 2.80735492206, floor(log_2(7)) = 2, #arrows = 2`
`n = 9, log_2(9) = 3.16992500144, floor(log_2(9)) = 3, #arrows = 3`

基本算法分析和 While 循环行为

Basic Algorithm Analysis and While Loop Behaviour

algorithm

time-complexity

asymptotic-complexity

big-theta