2个嵌套循环的时间复杂度
如果我通过两个嵌套的For循环进行输入
cin>>x;
for(i=0;i<x;i++)
{
cin>>y;
for(j=0;j<y;j++)
}
外环的复杂度是O（X），但是我对内环的时间复杂度感到困惑，因为Y是可变的。
共有1个答案
外循环的复杂性不是O（x），因为运行外循环所需的时间取决于输入的y值。
假设我们有一个序列y1，y2，。。。，yn是y的输入。然后第一个循环将进行y1运算，第二次迭代将对每个x迭代进行y2运算，依此类推。
现在让Y成为这个输入序列的最大值，那么外部循环的每次迭代最多需要Y操作。所以对于x迭代，每次最多进行Y运算，我们得到O（xY）。
可以进一步指定一个可能更小的函数类，但重要的是要记住，如果f
考虑到在这种情况下，不使用最大值确定输入将是最坏的情况。
此外，如果输入在所有循环之外，则会更准确，因为输入在大多数情况下不是一个恒定的操作。（不过这很简单，只需从文件或其他东西中输入y，然后用它来创建一个数组即可。）
-
我很难理解算法分析，尤其是下面的例子： 所以我的理解是，外循环是，当我乘以一个常量时，我不确定是否有任何区别。 不过，最让我困惑的是内部循环。我认为它是，因为j被常数递减，但我不确定和
-
这段代码的时间复杂度是多少？外循环运行n次，但我不确定内循环。如果内环对于i的每个值一直运行到n，它能是O（n^2）吗？
-
有三个嵌套的循环，如果循环增量为1，我可以找到复杂性，但是如果循环增量像这样i=c，我就糊涂了？ 第三个for循环的复杂度是m，但第一个for循环的复杂度是n/c，第二个for循环的复杂度是n==
-
这个问题是为了修改过去的试卷，如果我走上了正确的道路，我需要一些建议。 求出下面一段代码的时间复杂度，表示给定整数n的操作次数： 所以我认为外循环是，第一个内环是，第二个内环是。我只是想知道我是否有一个大致的想法，以及如何从这里继续前进。
-
我的困惑是- 如果我把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值一样，内部循环的运行次数也会减少 有人能给我解释一下吗？