我在StackOverflow上进行了一些搜索,并了解了直到j循环为止的复杂度,即 O(n 2 )。但是,由于嵌套了k循环,我感到困惑,因为为什么复杂度变为 O(n 3 )。有人可以帮我理解吗?
I have searched a bit on StackOverflow and have understood the complexity up to the point of the j-loop, which is O(n2). However with the nested addition of the k-loop, I am confused as why the complexity becomes O(n3). Can someone help me understand this?
据我了解,i循环有n次迭代,j循环有1 + 2 + 3 + ... + n迭代 n *(n + 1)/ 2 ,即 O(n 2 )
From my understanding, the i-loop have n iterations and the j-loop have 1+2+3+...+n iterations n*(n+1)/2 which is O(n2).
for(i = 1; i < n; i++) { for(j = i+1; j <= n; j++) { for(k = i; k <= j; k++) { // Do something here... } } }编辑:感谢您的所有帮助:) Balthazar,我已经写了一段代码,可以根据它们所在的循环来增加计数器的数量,这是一种循序渐进的粗略方法:
Thanks for all your help guys :) Balthazar, I have written a piece of code to which will increment counters depending on which loop they are in, kinda a crude way of step-by-step:
#include <iostream> int main(int argc, const char * argv[]) { int n = 9; int index_I = 0; int index_J = 0; int index_K = 0; for (int i = 1; i < n; i++) { for (int j = i+1; j <= n; j++) { for (int k = i; k <= j; k++) { index_K++; } index_J++; } index_I++; } std::cout << index_I << std::endl; std::cout << index_J << std::endl; std::cout << index_K << std::endl; return 0; }我将此代码从n = 2运行到n = 9,增量为1并具有以下顺序:
I ran this code from n=2 to n=9 with increments of 1 and have got the following sequence:
因此从计数器中可以看出:i = n-1给出O(n)的复杂度,并且j =((n-1)* n)/ 2给出复杂度 O(n 2 )。很难发现K的模式,但是已知K取决于J,因此:
From the counters, it can therefore be seen that: i = n-1 giving the complexity of O(n) and j = ((n-1)*n)/2 giving the complexity O(n2). A pattern for K was hard to spot but it is known that K depends on J, therefore:
k =((n + 4)/ 3)* j =(n *( n-1)*(n + 4))/ 6 给出 O(n 3 )
k = ((n+4)/3)*j = (n*(n-1)*(n+4))/6 giving a complexity of O(n3)
我希望这对以后的人们有所帮助。
I hope this will help people in the future.
EDIT2:谢谢Dukeling 进行格式化:)在最后一行中也发现了一个错误,现在已纠正
thanks Dukeling for the formatting :) Also found a mistake in the last line, corrected now
推荐答案如果您习惯于Sigma表示法,这是一种推断算法时间复杂度的正式方法(精确地是简单的嵌套循环):
If you're accustomed to Sigma Notation, here is a formal way to deduce the time complexity of your algorithm (the plain nested loops, precisely):
NB :公式简化可能包含错误。如果您检测到任何东西,请告诉我。
NB: the formula simplifications might contain errors. If you detect anything, please let me know.
更多推荐
此嵌套三重for循环的复杂性是什么?
发布评论