如何有效计算算法的时间复杂度？
How to effectively calculate an algorithm's time complexity?
我正在研究算法的复杂性，但我仍然无法确定某些算法的复杂性...好吧，我能够计算出基本的 O(N) 和 O(N^2) 循环，但是我在这样的例程中遇到了一些困难：
// What is time complexity of fun()?
int fun(int n)
{
int count = 0;
for (int i = n; i > 0; i /= 2)
for (int j = 0; j < i; j++)
count += 1;
return count;
}
好的，我知道有些人可以闭着眼睛计算这个，但是 我很想看看 "step" 的 "step" 如何 如果可能。
我第一次尝试解决这个问题是 "simulate" 输入并将值放在某种 table 中，如下所示：
for n = 100
Step i
1 100
2 50
3 25
4 12
5 6
6 3
7 1
好的，此时我假设这个循环是 O(logn)，但不幸的是，正如我所说，没有人通过 "step" 解决这个问题 "step" 所以最后我没有了解所有已完成的工作....
在内部循环的情况下，我可以构建某种 table，如下所示：
for n = 100
Step i j
1 100 0..99
2 50 0..49
3 25 0..24
4 12 0..11
5 6 0..5
6 3 0..2
7 1 0..0
我可以看到两个循环都在减少，我想可以根据上面的数据推导出一个公式...
有人可以澄清这个问题吗？ （答案是 O(n)）
让我们把这个分析分成几个步骤。
首先，从内部 for 循环开始。 很明显，这正好需要 i 个步骤。
接下来，考虑在算法 的过程中会采用哪些不同的值i。首先，考虑 n 是 2 的某个幂的情况。在这种情况下，i 从 n 开始，然后是 n/2，然后是 n/4，等等., 直到到达 1，最后到达 0 并终止。因为内层循环每次走i步，那么本例fun(n)的总步数正好是n + n/2 + n/4 + ... + 1 = 2n - 1.
最后，说服自己这可以推广到 2 的非幂。给定一个输入 n，找到大于 n 的最小 2 次方并将其命名为 m。显然，n < m < 2n，所以 fun(n) 比 4n - 1 少了 2m - 1 步。因此 fun(n) 是 O(n)。
另一种简单的查看方式是：
您的外循环在 n 处初始化 i（可以认为是 step/iterator），并在每次迭代后将 i 除以 2。因此，它执行 i/2 语句 log2(n) 次。因此，一种思考方式是，你的外循环 运行 log2(n) 次 。每当你将一个数字连续除以一个基数直到它达到 0 时，你就有效地执行了这个除法日志次数。因此，外循环是 O(log-base-2 n)
您的内循环迭代 j（现在是迭代器或步骤）从 0 到 i 外循环的每次迭代。 i 取 n 的最大值，因此你的内部循环将拥有的最长 运行 将从 0 到 n。因此，它是 O(n).
现在，您的程序 运行 是这样的：
Run 1: i = n, j = 0->n
Run 2: i = n/2, j = 0->n/2
Run 3: i = n/4, j = 0->n/4
.
.
.
Run x: i = n/(2^(x-1)), j = 0->[n/(2^(x-1))]
现在，运行嵌套循环的时间总是 "multiplies"，所以
O(log-base-2 n)*O(n) 为您的整个代码提供 O(n)
我正在研究算法的复杂性，但我仍然无法确定某些算法的复杂性...好吧，我能够计算出基本的 O(N) 和 O(N^2) 循环，但是我在这样的例程中遇到了一些困难：
// What is time complexity of fun()?
int fun(int n)
{
int count = 0;
for (int i = n; i > 0; i /= 2)
for (int j = 0; j < i; j++)
count += 1;
return count;
}
好的，我知道有些人可以闭着眼睛计算这个，但是 我很想看看 "step" 的 "step" 如何 如果可能。
我第一次尝试解决这个问题是 "simulate" 输入并将值放在某种 table 中，如下所示：
for n = 100
Step i
1 100
2 50
3 25
4 12
5 6
6 3
7 1
好的，此时我假设这个循环是 O(logn)，但不幸的是，正如我所说，没有人通过 "step" 解决这个问题 "step" 所以最后我没有了解所有已完成的工作....
在内部循环的情况下，我可以构建某种 table，如下所示：
for n = 100
Step i j
1 100 0..99
2 50 0..49
3 25 0..24
4 12 0..11
5 6 0..5
6 3 0..2
7 1 0..0
我可以看到两个循环都在减少，我想可以根据上面的数据推导出一个公式...
有人可以澄清这个问题吗？ （答案是 O(n)）
让我们把这个分析分成几个步骤。
首先，从内部 for 循环开始。 很明显，这正好需要 i 个步骤。
接下来，考虑在算法 的过程中会采用哪些不同的值i。首先，考虑 n 是 2 的某个幂的情况。在这种情况下，i 从 n 开始，然后是 n/2，然后是 n/4，等等., 直到到达 1，最后到达 0 并终止。因为内层循环每次走i步，那么本例fun(n)的总步数正好是n + n/2 + n/4 + ... + 1 = 2n - 1.
最后，说服自己这可以推广到 2 的非幂。给定一个输入 n，找到大于 n 的最小 2 次方并将其命名为 m。显然，n < m < 2n，所以 fun(n) 比 4n - 1 少了 2m - 1 步。因此 fun(n) 是 O(n)。
另一种简单的查看方式是：
您的外循环在 n 处初始化 i（可以认为是 step/iterator），并在每次迭代后将 i 除以 2。因此，它执行 i/2 语句 log2(n) 次。因此，一种思考方式是，你的外循环 运行 log2(n) 次 。每当你将一个数字连续除以一个基数直到它达到 0 时，你就有效地执行了这个除法日志次数。因此，外循环是 O(log-base-2 n)
您的内循环迭代 j（现在是迭代器或步骤）从 0 到 i 外循环的每次迭代。 i 取 n 的最大值，因此你的内部循环将拥有的最长 运行 将从 0 到 n。因此，它是 O(n).
现在，您的程序 运行 是这样的：
Run 1: i = n, j = 0->n
Run 2: i = n/2, j = 0->n/2
Run 3: i = n/4, j = 0->n/4
.
.
.
Run x: i = n/(2^(x-1)), j = 0->[n/(2^(x-1))]
现在，运行嵌套循环的时间总是 "multiplies"，所以 O(log-base-2 n)*O(n) 为您的整个代码提供 O(n)