时间复杂度嵌套循环
我很难理解算法分析，尤其是下面的例子：
for (int i = 1; i < n^3; i = 2*i){
for (int j = 6*n; j > 0; j = j-2){
}
}
所以我的理解是，外循环是O（nlogn），当我乘以一个常量时，我不确定n^3是否有任何区别。
不过，最让我困惑的是内部循环。我认为它是O（n），因为j被常数递减，但我不确定6*n和j
如果我是正确的，那么整个算法将是O（nlogng）？虽然不确定如何表达它的时间复杂度T（n）。
任何见解都将不胜感激。
共有1个答案
外部循环不是O（nlogn）——因为i在每个循环中乘以2，它是：2，4，8，16，32。。。这意味着需要一个日志（n^3）步骤才能使i达到n^3（日志的基数为2）。
更正式的：O（log（n^3））=O（3logn）=O（logn）
在内部循环中，j被初始化为6*n，并以2步的顺序下降。这意味着j达到零需要6n/2步。
更正式：O（6n/2）=O（3n）=O（n）
因此，代码部分的复杂性是O（n）*O（logn）=O（nlogn）
-
我的困惑是- 如果我把n+(n^2-1)*O(1)写成n+O(1)+O(1)+........+O(1)，那么我可以忽略低阶项，复杂性将是O(n)，但是另一个推理可以是一个常数的工作量正在做n^2次，所以时间复杂性应该是O(n^2) 在这个问题中也发生了类似的事情-带有if语句的嵌套循环的时间复杂度O(N):O(N^4)？
-
以下示例循环的时间复杂度为O（n^2），有人能解释为什么是O（n^2）吗？因为这取决于c的价值。。。 循环1--- 回路2--- 如果c=0；然后它运行无限次，就像增加c值一样，内部循环的运行次数也会减少 有人能给我解释一下吗？
-
对于下面的循环， 时间复杂度是多少，我应该怎么想？我的猜测是外环总共运行。内环运行次。因此，时间复杂度应该是。 我说得对吗？ 提前感谢。
-
如果我通过两个嵌套的For循环进行输入 外环的复杂度是O（X），但是我对内环的时间复杂度感到困惑，因为Y是可变的。
-
我正在努力找到确切的答案 我知道外环运行了n次。然后，第二个循环每次运行的次数不同，因为它从i开始： n（n-1）（n-2）。。。2 1. 但是，因为我们只关心最坏的情况（当i=n时），所以第二个循环将运行n-n次，因为它将从i=n开始。这当然没有意义，但这就是我被卡住的地方。我已经运行了这段代码，找到了序列的前四个元素：S=0 1 4 10。。。（其余部分不确定）。 抱歉，如果这不合理，但任何帮
-
有三个嵌套的循环，如果循环增量为1，我可以找到复杂性，但是如果循环增量像这样i=c，我就糊涂了？ 第三个for循环的复杂度是m，但第一个for循环的复杂度是n/c，第二个for循环的复杂度是n==