如下所示的嵌套循环的时间复杂度是多少：
1）
for (int i = 1; i <=n; i += 2) {
for (int j = 1; j <=n; j += 2) {
// some O(1) expressions
}
}
2）
for (int i = 1; i <=n; i += 3) {
for (int j = 1; j <=n; j += 3) {
// some O(1) expressions
}
}
一般来说：
for (int i = 1; i <=n; i += c) {
for (int j = 1; j <=n; j += c) {
// some O(1) expressions
}
}
真的是以下吗？
O（n c）
您的算法将执行(n / c) * (n /c)迭代。我们正在划分，因为我们在c每次迭代中都跳过字符。看到：
for (var i = 0; i <= n; i = i + 1)
将有n / 1迭代
for (var i = 0; i <= n; i = i + 2)
将有n / 2迭代
*请注意，结果将是底限。也就是说，如果n = 3和c = 2，它将仅执行一次（floor(3 / 2) == 1）
因此，我们可以将其概括为
（n / c）2 =（n 2 / c 2） = 1 / c 2 * n 2
请记住，Big O只对变化率感兴趣。由于c是常数，因此从计算中将其忽略。
因此，结果是：
O（1 / c 2 * n 2）= O（n 2）
本文收集自互联网，转载请注明来源。
如有侵权，请联系[email protected] 删除。
我来说两句