证明时间复杂度

证明时间复杂度

问题描述：

我正在尝试确定这两个函数的复杂度，其中 D 是一个整数，而 list 是一个整数列表:

I'm trying to determine the complexity of this two functions, where D in an integer and list is a list of integers:

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 是列表元素的数量，但我想以正式的方式证明它.

Intuitively, I think it has a O(n²) where n is the quantity of elements of list, but I'd like to proof it in a formal way.

答

第一个观察:solve 调用 doFunc，但反过来不行.因此，solve 的复杂度将取决于 doFunc 的复杂度，而不是相反.我们需要先弄清楚doFunc的复杂度.

First observation: solve calls doFunc, but not the other way around. Therefore, the complexity of solve will depend on the complexity of doFunc, but not the other way around. We need to figure out the complexity of doFunc first.

设 T(E, D, N) 是 doFunc 作为 E 的函数的时间复杂度，D 和列表中元素的数量 N.每次调用 doFunc 时，我们都会进行 N 次循环迭代，然后使用 E+1 调用 doFunc，D-1，列表不变.基于此，我们知道doFunc的时间复杂度由以下递归公式给出:

Let T(E, D, N) be the time complexity of doFunc as a function of E, D and the number of elements N in the list. Every time doFunc is called, we do N iterations of the loop and then invoke doFunc with E+1, D-1, and the list unchanged. Based on this, we know that the time complexity of doFunc is given by the following recursive formula:

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

这里，a 和 b 是一些需要确定的常量.

Here, a and b are some constants to be determined.

现在我们需要这个递归公式的基本情况.我们的基本情况，唯一不递归的情况是 D .假设 D 是非负的，这意味着 D = 0 是基本情况.我们得到以下附加要求:

Now we need a base case for this recursive formula. Our base case, the only time we don't recurse, is when D <= 0. Assuming that D is non-negative, this means D = 0 is the base case. We get the following additional requirement:

T(E, 0, N) = c

这里，c 是一些待确定的常数.

Here, c is some constant to be determined.

将所有这些放在一起，我们可以为 D 的不同值列出几个值，看看我们是否可以识别一个模式:

Putting this all together, we can list out a few values for different values of D and see if we can identify a pattern:

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.我们可以看到这个公式满足基本情况，我们可以检查它是否也满足递归部分(试试这个).因此，这是我们的功能.

Based on this, we can guess that T(E, D, N) = c + Db + aDN for some constants a, b, c. We can see that this formula satisfies the base case and we can check that it also satisfies the recursive part (try this). Therefore, this is our function.

假设 E、D 和 N 都是独立且自由变化的，则 doFunc 的时间复杂度为最好呈现为 O(c + Db + aDN) = O(DN).

Assuming E, D and N are all independent and vary freely, the time complexity of doFunc is best rendered as O(c + Db + aDN) = O(DN).

由于solve为列表中的每个元素调用一次doFunc，其复杂度只是doFunc的N倍代码>，即O(DN^2).

Since solve calls doFunc once for each element in the list, its complexity is simply N times that of doFunc, i.e., O(DN^2).

相关推荐