我是新来的时间复杂性,我似乎无法理解最后得到这个背后的逻辑:
100 (n(n+1) / 2)
对于此功能:
function a() {
int i,j,k,n;
for(i=1; i<=n; i++) {
for(j=1; j<=i; j++) {
for(k=1; k<=100; k++) {
print("hello");
}
}
}
}
这是我如何理解它的算法:
i = 1, 2, 3, 4...n
j = 1, 2, 3, 4...(dependent to i, which can be 'n')
k = 1(100), 2(100), 3(100), 4(100)...n(100)
= 100 [1, 2, 3, 4.....]
如果我使用上面的这个算法来模拟最终方程,我会得到这个结果:
结束方程:
100 (n(n+1) / 2)
模拟
i = 1, 2, 3, 4... n
j = 1, 2, 3, 4... n
k = 100, 300, 600, 10000
我通常在 youtube 上研究这些并得到 Big O、Omega 和 Theta 的想法,但是当谈到这个时,我无法弄清楚它们如何以我给出的等式结束。请帮助,如果您有一些最佳实践,请分享。
编辑:
至于我自己对答案的假设,它认为应该是这个:
100 ((n+n)/2) or 100 (2n / 2)
来源:
https://www.youtube.com/watch?v=FEnwM-iDb2g
At around: 15:21
最佳答案
我想你有 i
和 j
正确,只是不清楚你为什么说 k = 100, 200, 300...
在每个循环中,k
来自 1
至 100
.
所以让我们首先考虑一下内部循环:
k from 1 to 100:
// Do something
内循环是 O(100) = O(1) 因为它的运行时不依赖于
n
.现在我们分析外循环:i from 1 to n:
j from 1 to i:
// Do inner stuff
现在让我们数出多少次
Do inner stuff
执行:i = 1 1 time
i = 2 2 times
i = 3 3 times
... ...
i = n n times
这是我们的经典triangular sum
1 + 2 + 3 + ... n = n(n+1) / 2
.因此,外部两个循环的时间复杂度为 O(n(n+1)/2) 减少到 O(n^2) .整个事情的时间复杂度是 O(1 * n^2) = O(n^2) 因为嵌套循环会增加复杂性(假设内循环的运行时间与外循环中的变量无关)。请注意,如果我们没有在各个阶段减少,我们将剩下 O(100(n)(n+1)/2) ,相当于 O(n^2) 因为大 O 符号的特性。
一些提示:
您要求提供一些最佳实践。以下是我在分析您发布的示例时使用的一些“规则”。
如果您可以将代码分解成更小的部分(与我们分析
k
循环与外部循环相同的方式),那么您可以利用嵌套规则来找到组合的复杂性。关于 Omega/Theta 的说明:
Theta 是时间复杂度的“精确界限”,而 Big-O 和 Omega 分别是上限和下限。因为没有随机数据(就像在排序算法中那样),我们可以得到时间复杂度的精确界限,并且上限等于下限。因此,在这种情况下,我们使用 O、Omega 或 Theta 没有任何区别。
关于time-complexity - 理解时间复杂度 : iterative algorithm,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/51924259/