嵌套for循环的时间复杂度
以下示例循环的时间复杂度为O（n^2），有人能解释为什么是O（n^2）吗？因为这取决于c的价值。。。
循环1---
for (int i = 1; i <=n; i += c)
{
for (int j = 1; j <=n; j += c)
{
// some O(1) expressions
}
}
回路2---
for (int i = n; i > 0; i -= c)
{
for (int j = i+1; j <=n; j += c)
{
// some O(1) expressions
}
}
如果c=0；然后它运行无限次，就像增加c值一样，内部循环的运行次数也会减少
有人能给我解释一下吗？
共有3个答案
对于每个固定的c，时间是O（n^2）。除非c=0，否则迭代次数大致为最大值（n^2/c^2，n^2）。n^2/c^2是O（n^2）代表每一个固定的n。
如果您的代码中c在循环过程中被更改，您可能会得到不同的答案。
Big-O表示法是算法复杂性的相对表示。
Big-O没有说明你的算法在任何情况下会进行多少次迭代。
它说，在最坏的情况下，你的算法将进行n平方计算。如果你需要比较两种算法，这很有用。
在你的代码中，如果我们假设c是一个常量，那么它可以从Big-O符号中忽略，因为Big-O是关于比较和事物如何缩放的。常量不起作用。
但当c不是常数时，正确的大O符号应该是O（n^2/c^2）。
阅读Cletus对Big-O的精彩解释。
代码的每一部分都需要一个时间O（n^2/c^2）。c在这里可能被认为是一个严格的正常数，因此O（n^2/c^2）=O（n^2）。但是这都取决于上下文...
-
我正在努力找到确切的答案 我知道外环运行了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==
-
这个问题是为了修改过去的试卷，如果我走上了正确的道路，我需要一些建议。 求出下面一段代码的时间复杂度，表示给定整数n的操作次数： 所以我认为外循环是，第一个内环是，第二个内环是。我只是想知道我是否有一个大致的想法，以及如何从这里继续前进。
-
我很难理解算法分析，尤其是下面的例子： 所以我的理解是，外循环是，当我乘以一个常量时，我不确定是否有任何区别。 不过，最让我困惑的是内部循环。我认为它是，因为j被常数递减，但我不确定和
-
这段代码的时间复杂度是多少？外循环运行n次，但我不确定内循环。如果内环对于i的每个值一直运行到n，它能是O（n^2）吗？
-
我的困惑是- 如果我把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)？