如何计算复杂程度？

问题描述

我想我知道这两个代码的复杂性，但是我只是找不到合适的方程式来证明这一点。
我假设的第一个是O（loglogn）。第二个是O（n ^ 2）。

I think I know the complexity of these 2 codes but I simply cant find the right equations to prove it.The first one I assume is O(loglogn). The second one is O(n^2).

def f1(lst):
    i=2
    while i<len(lst):
        print(lst[i])
        i **= 2

第二个代码：

def f2(lst):
    i = len(lst)
    while i>0:
        for j in range(i):
            for k in range(10**5, j, -5):
                print(i)
        i -= 2

推荐答案

我认为您可以先尝试获得递归方程，然后再使用master定理或其他解决递归方程的方法。对于第一个，我们使用lst的长度作为参数。

I think you can try to get the recursive equation first, and then use master theorem or something else to solve the recursive equations. For the first one, we use the length of the lst as the parameter.

def f1(lst1): #len(lst2)=N
    i=2
    while i<len(lst1):
        print(lst1[i])
        i **= 2

def f1(lst2): #len(lst2)=N^2
    i=2
    while i<len(lst2):
        print(lst2[i])
        i **= 2

您会注意到，第二个仅执行一次。因此您得到

you will notice that the second one will execute only once more than the first one. so you get

T（N ^ 2）= T（N）+1。

T(N^2)=T(N)+1.

为简单起见，假设N ^ 2 = 2 ^ k，

For simplification, just suppose N^2=2^k,

然后T（2 ^ k） = T（2 ^（k / 2））+ 1，令f（k）= T（2 ^ k），

then T(2^k)=T(2^(k/2))+1,let f(k)=T(2^k),

然后f（k）= f（ k / 2）+1，

then f(k)=f(k/2)+1,

具有主定理，T（N ^ 2）= f（k）= log（k）= log（log（2 ^ k））= log（log（N ^ 2））。

with the master theorem, T(N^2) = f(k) = log(k) = log(log(2^k)) = log(log(N^2)).

最后我们得到T（N）= O（loglog（N））。

we get T(N) = O(loglog(N)) at last.

这篇关于如何计算复杂程度？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！