如何根据操作次数计算时间复杂度 [英] How to work out the time complexity in terms of the number of operations
问题描述
所以我想知道如何根据操作数计算出一段代码的时间复杂度（ T（n）），例如下面的代码。 / p>
so I was wondering how would I work out the time complexity (T(n)) of a piece of code, for example, the one below, in terms of the number of operations.
for( int i = n; i > 0; i /= 2 ) {
for( int j = 1; j < n; j *= 2 ) {
for( int k = 0; k < n; k += 2 ) {
... // constant number of operations
}
}
}
我确定它很简单，但这我的讲师没有很好地讲授这个概念，我真的很想知道如何解决时间的复杂性！
I'm sure its simple but this concept wasn't taught very well by my lecturer and I really want to know how to work out the time complexity!
预先感谢您！
推荐答案
要解决此问题，一种方法是分别分解三个循环的复杂性。
To approach this, one method is to breakdown the complexity of your three loops individually.
我们可以看到的一个主要观察结果是：
A key observation we can make is that:
（P）：每个循环中的步数不取决于
让我们打电话
-
f（n）外循环中合计的操作数（1） $在中间内部循环（2）中的b $ b -
g（n） -
h（n）在最内部的循环（3）中。
f(n)the number of operations aggregated in the outer loop (1)g(n)in the intermediate inner loop (2)h(n)in the most inner loop (3).
for( int i = n; i > 0; i /= 2 ) { // (1): f(n)
for( int j = 1; j < n; j *= 2 ) { // (2): g(n)
for( int k = 0; k < n; k += 2 ) { // (3): h(n)
// constant number of operations // => (P)
}
}
}
步数
i 获取值 n ， n / 2 ， n / 4 等...直到达到 n / 2 ^ k ，其中 2 ^ k 大于 n （ 2 ^ k> n ），因此 n / 2 ^ k = 0 ，此时退出循环。
Number of steps
i gets the values n, n/2, n/4, ... etc. until it reaches n/2^k where 2^k is greater than n (2^k > n), such that n/2^k = 0, at which point you exit the loop.
另一种说法是，您具有第1步（ i = n ），步骤2（ i = n / 2 ），步骤3（ i = n / 4 ），...步骤 k-1 （ i = n / 2 ^（k -1）），然后退出循环。这些是 k 步。
Another way to say it is that you have step 1 (i = n), step 2 (i = n/2), step 3 (i = n/4), ... step k - 1 (i = n/2^(k-1)), then you exit the loop. These are k steps.
现在 k ？观察 n-1< = 2 ^ k< n< => log2（n-1）< = k< log2（n）< = INT（log2（n-1））< = k< = INT（log2（n））。这使得 k = INT（log2（n））或松散地说 k = log2（n）。
Now what is the value of k? Observe that n - 1 <= 2^k < n <=> log2(n - 1) <= k < log2(n) <= INT(log2(n - 1)) <= k <= INT(log2(n)). This makes k = INT(log2(n)) or loosely speaking k = log2(n).
每个步骤的费用
现在每个步骤要执行多少操作？
在步骤 i 中，它是 g（i）= g（n）根据我们选择的符号和属性（P）。
At step i, it is g(i) = g(n) according to the notations we chose and the property (P).
步数
您有步骤（1）（ j = 1 ） ，步骤（2）（ j = 2 ），步骤（3）（ j = 4 ）等，直到您到达步骤（p）（ j = 2 ^ p ），其中 p 被定义为最小整数，使得 2 ^ p> n 或松散地说 log2（n）。
Number of steps
You have step (1) (j = 1), step (2) (j = 2), step (3) (j = 4), etc. until you reach step (p) (j = 2^p) where p is defined as the smallest integer such that 2^p > n, or loosely speaking log2(n).
成本每个步骤
步骤 j 的成本为 h（j）= h（n）根据我们选择的符号和属性（P）。
Cost of each step
The cost of step j is h(j) = h(n) according to the notations we chose and the property (P).
步骤数
再次，我们计算一下步骤：（1）： k = 0 ，（1）： k = 2 ，（2）： k = 4 ，...， k = n-1或k = n -2 。这相当于 n / 2 个步骤。
Number of steps
Again, let's count the steps: (1):k = 0, (1):k = 2, (2):k = 4, ..., k = n - 1 or k = n - 2. This amounts to n / 2 steps.
每个步骤的费用
由于（P），它是恒定的。我们将此常量称为 K 。
Cost of each step
Because of (P), it is constant. Let's call this constant K.
总计操作数为
T(n) = f(n) = sum(i = 0, i < log2(n), g(i))
= sum(i = 0, i < log2(n), g(n))
= log2(n).g(n)
= log2(n).sum(j = 0, j < log2(n), h(j))
= log2(n).log2(n).h(n)
= log2(n).log2(n).(n/2).K
所以 T（n）=（K / 2）。（log2（n））^ 2.n
这篇关于如何根据操作次数计算时间复杂度的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
