證明的時間複雜度

Question

我試圖確定這兩個功能，其中的整數和列表d是一個整數列表的複雜性：

def solve(D, list): 
    for element in List: 
     doFunc(element, D, list) 

def doFunc(element, D, list): 
    quantityx = 0 
    if(D > 0): 
    for otherElement in list: 
     if otherElement == element: 
     quantityx += 1 
    return quantityx + (doFunc ((element+1), (D-1), list)) 
    return 0 

直覺，我覺得它有一個O（N²）其中n是列表元素的數量，但我想以正式方式證明它。

Answer 1

首先觀察：solve調用doFunc，但不是相反。因此，solve的複雜性將取決於doFunc的複雜性，但不是相反。我們首先需要弄清楚doFunc的複雜性。

設T(E, D, N)是doFunc的時間複雜度爲E，D的功能，並在列表中的元素N的數量。每次調用doFunc時，我們都做N循環的迭代，然後調用doFunc與E+1,D-1，並且列表不變。在此基礎上，我們知道，doFunc時間複雜度由下面的遞歸式給出：

T(E, D, N) = aN + b + T(E+1, D-1, N)

這裏，a和b一些常數確定。

現在我們需要這個遞歸公式的基本情況。我們的基本情況是唯一一次不緩存的情況，即D <= 0。假設D是非負數，這意味着D = 0是基本情況。我們得到以下額外要求：

T(E, 0, N) = c

這裏，c一些常數確定。

把所有這些組合起來，我們可以列出幾個值的D不同的值，看看是否我們可以找出一個規律：

D T(E, D, N) 
0 c 
1 c + b + aN 
2 c + 2b + 2aN 
3 c + 3b + 3aN 
... 
k c + kb + kaN 

在此基礎上，我們可以猜測，T(E, D, N) = c + Db + aDN一些常量a, b, c 。我們可以看到這個公式滿足基本情況，我們可以檢查它是否滿足遞歸部分（試試這個）。因此，這是我們的功能。

假設E，D和N都是獨立的，並自由地變化，的doFunc時間複雜度爲O(c + Db + aDN) = O(DN)最好呈現。

由於solve呼叫doFunc一次列表中的每個元素，它的複雜性僅僅是的doFuncN倍，即O(DN^2)。