C，西格玛的时间复杂度? [英] C, Time complexity of sigma?

问题描述

如何找到以下代码的时间复杂度:

How may I find the time complexity of the following code:

(很抱歉添加图像，一旦我可以使用笔记本电脑，我将重新编辑我的问题)

我到目前为止所做的事情:

第一个循环迭代n次，第二个循环i次，第三个log(i * j)次，所以简化后得到:

The first loop iterates n times, the second i times and the third log(i*j) times, So after simplifying I got:

i * log i + n *时从i = 0到n的Sigma(log i时从j = 0到i的Sigma)

Sigma from i=0 to n for i*log i + n * (Sigma from j=0 to i for log i)

但是为什么这等于O(n ^ 2 log(n))?

But why this is equal to O(n^2 log(n))?

推荐答案

方法1 :

在最坏的情况下:

第一个循环执行n次. 第一个循环的时间复杂度= O(n)

First loop executes for n time. Time Complexity of first loop = O(n)

第一和第二循环的时间复杂度 = 1 + 2 + 3 + 4 + ... + n = O(n*(n+1)/2) = O(n^2)

Time Complexity of first and second loop = 1 + 2 + 3 + 4 + ... + n = O(n*(n+1)/2) = O(n^2)

我们可以计算第三循环的复杂度并将其乘以先前计算的复杂度，因为第三循环不会影响(更改第一或第二循环的任何变量)先前循环的变量.

We can calculate complexity of 3rd loop and multiply this with the previously calculated complexity because the third loop does not affect (change any variable of first or second loop) the previous loops' variable.

第三次循环的时间复杂度= log(i*j)

Time Complexity of third loop = log(i*j)

= log(i*j) = log(n*2 ) = 2log(n)

= log(n)

最终复杂度= O(n^2 * (log(n))

方法2 :

如果我们用对数(i * j)来可视化它.看起来像这样.

If we visualize this in terms of log(i*j). It will look something like this.

log(1) + log(2) + log(3) + ... + log(n*(n-1))

=

n*log((n-1)!)

使用字符串近似值-引用 log(n！)值

Refer log(n!) value using string approximation - stackoverflow for below result

log((n-1)!) = nlogn

最终复杂度:

O(n* nlog(n))

=

O(n^2)*log(n)

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