时间复杂度是O（N），而不是O（N*i）。
for (int i = 0; i < N; i++) { a[i] *= 2; for (int j = 0; j < i; j++) d[i][j] = a[i] * c[j]; }
如果有人能给我指出正确的方向，我将不胜感激。
rdrgkggo1#
如果嵌套循环没有迭代相同数量的外部循环，这并不重要。总的时间复杂度是O(N^2)。
O(N^2)
C = O(N) + O(0 + 1 + 2 + ... + N - 1)
O(N)是a[i] *= 2，右边部分是内部循环。这是算术平均级数的总和：
O(N)
a[i] *= 2
C = O(N) + O(N * (N - 1) / 2) = O(N) + O(N^2/2 - N/2) = O(N) + O(N^2) + O(N^2)
hjqgdpho2#
因为这里的循环很简单，所以很容易计算完成的所有操作。a[i] *= 2被执行N次。d[i][j] = a[i] * c[j]是这样做的：
N
d[i][j] = a[i] * c[j]
i==0
i==1
i==N-1
总数为：N + 0 + 1 + ... + N-1 = N + (N-1)(N-2)/2 = (1/2)(N^2) - N/2 + 1。
N + 0 + 1 + ... + N-1
N + (N-1)(N-2)/2
(1/2)(N^2) - N/2 + 1
对于O()，我们只考虑最高功率，忽略常数系数，这里是O(N^2)。
O()
为什么会这样？我们想知道当N很大时会发生什么。例如：N = 1,000 =>确切的数字是(1/2)(N^2) - N/2 + 1 = 499,501。N = 10,000 =>确切的数字是(1/2)(N^2) - N/2 + 1 = 49,995,001。我们看到，对于N大10倍，结果大约大100倍。为**O(N^2)**。
N = 1,000
499,501
N = 10,000
49,995,001
我们可以做得更短，重读代码：
在N上有一个循环，在一个由i和i限制的循环内，循环像N一样变化。这是一个**O(N^2)**进程。
i
2条答案
按热度按时间rdrgkggo1#
如果嵌套循环没有迭代相同数量的外部循环，这并不重要。总的时间复杂度是
O(N^2)。O(N)是a[i] *= 2，右边部分是内部循环。这是算术平均级数的总和：hjqgdpho2#
因为这里的循环很简单，所以很容易计算完成的所有操作。
a[i] *= 2被执行N次。d[i][j] = a[i] * c[j]是这样做的：i==0：0次i==1：1次i==N-1：N-1次。总数为：
N + 0 + 1 + ... + N-1=N + (N-1)(N-2)/2=(1/2)(N^2) - N/2 + 1。对于
O()，我们只考虑最高功率，忽略常数系数，这里是O(N^2)。为什么会这样？我们想知道当
N很大时会发生什么。例如：
N = 1,000=>确切的数字是(1/2)(N^2) - N/2 + 1=499,501。N = 10,000=>确切的数字是(1/2)(N^2) - N/2 + 1=49,995,001。我们看到，对于
N大10倍，结果大约大100倍。为**O(N^2)**。我们可以做得更短，重读代码：
在
N上有一个循环，在一个由i和i限制的循环内，循环像N一样变化。这是一个**O(N^2)**进程。