下面代码的时间复杂度是多少? [英] What is the time complexity of the code below?

问题描述

sum =0;

            for (int i=1; i<n; i++) {

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

                sum = sum +j;

              }

            }

在上面的外循环中，变量i从1到n运行，因此外循环的复杂度为O(n).这解释了 O(n logn) 复杂度的 n 部分.

In the above outer loop , The variable i runs from 1 to n, thus making complexity of outer loop as O(n). This explains the n part of O(n logn) complexity.

但是对于外部，当我们看到 j 从 1 运行到 n/i 时，这意味着每当 i 为 1 时，复杂度为 n 所以我猜内部时间复杂度也应该是 O(n).

But for the outer part when we see then j runs from 1 to n/i, meaning whenever i is 1 , the complexity is n so i guess the inner time complexity should also be O(n).

使总时间复杂度为 O(n*n)=O(n^2).

Making the total time Complexity as O(n*n)=O(n^2).

推荐答案

这是您可以使用 Sigma 符号执行的操作:

This is what you can do using Sigma notation:

与 H_{n-1} 是调和函数:

With H_{n-1} is the harmonic function:

寻找谐波级数的大 O

这篇关于下面代码的时间复杂度是多少?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！