我试图计算以下循环的时间复杂度，其中1<=N<=100000
我们可以假设n=100000
环路1
for(int i=0; i<n; i++)
{
}
loop2
for(int i=0; i<n; i++)
{
for(int j=0; j<n; j++)
{
}
}
环3
for(int i=0; i<n; i++)
{
for(int j=i; j<n; j++)
{
}
}
环4
for(int i=0; i<n; i+=2)
{
}
环5
for(int i=0; i<n; i+=2)
{
for(int j=0; j<n; j++)
{
}
}
环6
for(int i=0; i<n; i+=2)
{
for(int j=0; j<n; j+=2)
{
}
}
loop7
for(int i=0; i<n; i+=2)
{
for(int j=i; j<n; j+=2)
{
}
}
loop8
for(int i=0; i<n; i*=2)
{
}
环9
for(int i=0; i<n; i*=2)
{
for(int j=0; j<n; j++)
{
}
}
loop10
for(int i=0; i<n; i*=2)
{
for(int j=i+1; i<n; j*=2)
{
}
}
我已经在不同的平台上搜索过了，但是我没有找到所有的解决方案。 因此，我正在研究如何计算上述代码的时间和空间复杂度，以及计算它们的过程。
如果我没弄错的话，复杂性是O(n^2)。 原因是当我们计算复杂度时，我们总是采用最昂贵的计算公式。
例如； O(n^2)的原因如下:
for(int i=0; i<n; i++)
{
for(int j=0; j<n; j++)
{
}
}
何处为
n=1->； n计算
n=2->； n计算
。。。
n=n->； n计算。 因此，O(n^2)。
如果我们看看其他循环，例如:
for(int i=0; i<n; i++)
{
}
O(n)
for(int i=0; i<n; i+=2)
{
for(int j=0; j<n; j++)
{
}
}
小于O(n^2)。
你总是取最高的顺序，也就是O(n^2)。
这似乎是一个家庭作业问题，而你似乎被误导了，所以我将给予指导但不是完整的答案:
其中1<=N<=100000
这没道理。 时间复杂性本质上是关于当边界（在本例中为n)接近无穷大时运行时如何缩放。 因此，将n限定为有限数，然后要求时间复杂度是没有意义的。
如何计算上述代码的时间和空间复杂度
空间复杂度是内存使用的缩放方式，但是您只有2个变量（因为循环是空的），所以所有的空间复杂度都是恒定的，即O(1)。 让我们计算一对:
for(int i=0; i<n; i++)
{
}
这个循环运行n次，这意味着它的时间复杂度为O(n)。
（不在你的列表中，但重要）
for(int i=0; i<17 * n + 27; i++)
{
}
这个循环运行17*n+27次，但是它仍然像n一样缩放。 为什么？ 17*n明显比27增长得快，因此17*n随着n接近无穷大而成为支配项，并且我们在渐近分析中不关心常数因子，因此17*n等价于n。 因此，时间复杂度为O(n)。
for(int i=0; i<n; i*=2)
{
}
这一次，您需要一些数学来计算循环运行了多少次。 我不会告诉你它到底是什么，但看看对数是如何工作的。
for(int i=0; i<n; i++)
{
for(int j=0; j<n; j++)
{
}
}
这是一个嵌套循环。 外环运行O(n)次，内环对外环的每个环运行O(n)次。 因此，时间复杂度为O(n*n)或O(n^2)。
