代码之家 › 专栏 › 技术社区 › nehacharya

这个代码的时间复杂度是O(n^2)还是O(nlogn)?

big-o time-complexity algorithm

nehacharya · 技术社区 · 2 年前

for (int i = 1; i <= n; i++) {
   for (int j = 1; j <= n; j += i) {
       // some code
   }
}

外循环绝对运行 n 时间。在假设n=8的内环的情况下,

我很困惑复杂性是否应该 logn 或 n 用于内环。任何帮助都将不胜感激!

1 回复 | 直到 2 年前

Berthur Sercan 2 年前

外部循环从 i = 1 到 n 步长为 1 因此,外部循环执行 n 时间-线性时间复杂性。

内部循环从 j = 1 到 n 步长为 i .步长 我 取决于 我 在外环中。

正如您的表格所示;

这些迭代的总和变为:

n + n/2 + n/3 + ... + 1

如果我们考虑 n ,我们得到谐波级数:

1 + 1/2 + 1/3 + ... 1/n

其时间复杂度近似为 log(n) .你可以在这里看到更详细的解释 https://stackoverflow.com/a/25905474/12974735

所以,你的代码总共有 O(n log(n)) 时间复杂性。

推荐文章

Matthew · 发现程序的时间复杂性

2 年前

TreasureGhost · 以下函数的时间复杂度是多少

2 年前

Abdullah Kassar · std::upper_bound()是线性的吗?c++

2 年前

user129393192 · 这个问题的最优算法是什么?

2 年前

3366784 · 使用序列初始化字符串的时间复杂度是多少?

2 年前

nehacharya · 这个代码的时间复杂度是O(n^2)还是O(nlogn)?

2 年前

control plane · ruby中链表上size调用的时间复杂性

2 年前

learner · 查找最长的子字符串

2 年前

hackrack · 在javascript中,如何返回时间复杂度为O(n)的相同字母元素?

7 年前

data-oil · 在字符串列表中搜索的高效快捷方法

7 年前