如何找到下面提到的算法的执行时间？
How to find the execution time of the below mentioned algorithm?
假设模块A的运行时间为常数M，N为输入数据的大小
1. Set J:=N.
2. Repeat Steps 3 and 4 while J>1.
3. Module A.
4. Set J:=J/2.
[End of Step 2 loop.]
5. Return.
TL;DR
这个算法的时间复杂度在O(log(n))
说明
- 由于模块A以恒定时间M运行，我们可以说它的运行时间是O(1)
- 同样适用于指令
Set J:=J/2，它在 O(1) 中运行
- 假设第 2 行的循环总共运行 K 次。所以在循环完成迭代 K 次后，我们将得到 J = 1。
- 循环的第 1 次迭代后，我们还剩下 N / 2 次迭代。在第二个之后我们有 N / 4。第3个N / 8，第4个N / 16，依此类推
- 在 K 次迭代后（当循环完成迭代时）我们将得到 J = 1 = N / (2^K).
- 所以 N / (2^K) = 1，这给了我们 N = 2^K。因此迭代次数为K = log2(N)
- 循环每次迭代的指令需要 O(1)，我们最终得到总共 O(log(N))
备注
- 这是一个article that illustrates the concept by using it in the Binary Search Algorithm
假设一个数除以二可以在常数时间内完成，该算法的时间复杂度为O(log N)。对于（非常）大的数字，除以 2 需要一些额外的时间：O(log K) 和 K 要除的值。
算法在J小于或等于1时停止。所以这意味着如果 J=2，那么它需要 M+1 步（计算模块的时间，将 J 除以二，让我们这里假设除以二需要常数时间）。
现在对于 J=2*K（使用 K 一个变量），它再次需要 M+1 步来完成循环，加上它所花费的时间用J=K解决问题。
所以这意味着我们得到以下等式：
T(1) = 0
T(N) = T(N/2) + M + 1
因此我们看到工作量随着迭代次数呈线性增长，并且迭代次数有一个上限log 2N：如果我们要执行K步，那么初始的N在[=48之间=]2K-1+1 和 2K.
所以这意味着总步数受限于：
T(N) = (M+1) * log2(N)
M 是常量，所以这意味着 M+1 是常量，因此 变量 部分是 log2(N)。这是一个 O(log N).
严格来说，如果 N 可以非常大，以至于我们需要任意数量的内存，那么除法就不是常数。如果我们使用二进制数系统，我们可以将 O(log K) 中的位与 K 相除的数（和 log2k位数).
在这种情况下，需要采取以下步骤：
T(1) = 0
T(N) = T(N/2) + M + log2(N)
使用 K 次迭代，步数受限于：
K
---
\
/ log2(I) + M
---
I=1
log2(i)与i的总和来自1 到 k 等于 log2(k!)，这上限为 O(k log k)。由于步数 k 受 O(log N) 约束，因此这意味着划分的总时间复杂度为 O(log N × log(log N))。所有调用模块的总时间复杂度保持O(M×log N) 所以O(log N)，所以时间复杂度为O(log N × (1+log(log N)))，或更简单的 O(log N + log N×log(log N)).
然而，可以稍微改变算法，这样我们就不必明确地执行这些除法：我们可以使用某种游标，每次都向前移动一步直到 N 为 "exhausted"，在这种情况下，时间复杂度再次为 O(log N).
假设模块A的运行时间为常数M，N为输入数据的大小
1. Set J:=N.
2. Repeat Steps 3 and 4 while J>1.
3. Module A.
4. Set J:=J/2.
[End of Step 2 loop.]
5. Return.
TL;DR
这个算法的时间复杂度在O(log(n))
说明
- 由于模块A以恒定时间M运行，我们可以说它的运行时间是O(1)
- 同样适用于指令
Set J:=J/2，它在 O(1) 中运行
- 假设第 2 行的循环总共运行 K 次。所以在循环完成迭代 K 次后，我们将得到 J = 1。
- 循环的第 1 次迭代后，我们还剩下 N / 2 次迭代。在第二个之后我们有 N / 4。第3个N / 8，第4个N / 16，依此类推
- 在 K 次迭代后（当循环完成迭代时）我们将得到 J = 1 = N / (2^K).
- 所以 N / (2^K) = 1，这给了我们 N = 2^K。因此迭代次数为K = log2(N)
- 循环每次迭代的指令需要 O(1)，我们最终得到总共 O(log(N))
备注
- 这是一个article that illustrates the concept by using it in the Binary Search Algorithm
假设一个数除以二可以在常数时间内完成，该算法的时间复杂度为O(log N)。对于（非常）大的数字，除以 2 需要一些额外的时间：O(log K) 和 K 要除的值。
算法在J小于或等于1时停止。所以这意味着如果 J=2，那么它需要 M+1 步（计算模块的时间，将 J 除以二，让我们这里假设除以二需要常数时间）。
现在对于 J=2*K（使用 K 一个变量），它再次需要 M+1 步来完成循环，加上它所花费的时间用J=K解决问题。
所以这意味着我们得到以下等式：
T(1) = 0
T(N) = T(N/2) + M + 1
因此我们看到工作量随着迭代次数呈线性增长，并且迭代次数有一个上限log 2N：如果我们要执行K步，那么初始的N在[=48之间=]2K-1+1 和 2K.
所以这意味着总步数受限于：
T(N) = (M+1) * log2(N)
M 是常量，所以这意味着 M+1 是常量，因此 变量 部分是 log2(N)。这是一个 O(log N).
严格来说，如果 N 可以非常大，以至于我们需要任意数量的内存，那么除法就不是常数。如果我们使用二进制数系统，我们可以将 O(log K) 中的位与 K 相除的数（和 log2k位数).
在这种情况下，需要采取以下步骤：
T(1) = 0
T(N) = T(N/2) + M + log2(N)
使用 K 次迭代，步数受限于：
K
---
\
/ log2(I) + M
---
I=1
log2(i)与i的总和来自1 到 k 等于 log2(k!)，这上限为 O(k log k)。由于步数 k 受 O(log N) 约束，因此这意味着划分的总时间复杂度为 O(log N × log(log N))。所有调用模块的总时间复杂度保持O(M×log N) 所以O(log N)，所以时间复杂度为O(log N × (1+log(log N)))，或更简单的 O(log N + log N×log(log N)).
然而，可以稍微改变算法，这样我们就不必明确地执行这些除法：我们可以使用某种游标，每次都向前移动一步直到 N 为 "exhausted"，在这种情况下，时间复杂度再次为 O(log N).