示例代码计算复杂度的确定

Question

我给你三个短码：

第一个代码：

procedure Proc (n:integer)
  begin
  if n>0 then
    begin
    writeln('x')
    Proc(n-2)
     writeln('*');
     Proc(n-2)
     end 
   end

第二个代码：

procedure Proc (n:integer)
  begin
  if n>0 then
    begin
    writeln('*');
    Proc(n-1)
    end 
   end

第三个密码：

procedure Proc (n:integer)
  begin
  if n>0 then
    begin
    writeln('x')
    Proc(n/2)
     writeln('*');
     Proc(n/2)
     end 
   end

我想知道如何确定我给出的每个代码的计算复杂度，因为它将帮助我更好地理解..有人可以编写一个算法来逐步确定示例代码的计算复杂度，并这样做以便可以将此算法应用于其他代码示例？

Answer 1

第一个问题：假设你知道对于n - 2的值，Proc被调用了T(n-1)次。因此，对于 n 的值，T(n) = 1 + 2T(n-2)，因为对 Proc(n) 的一次调用会依次调用 Proc(n-2) 两次。 T(n) = 1 + 2T(n-2) 是汉诺塔的变体，即 T(n) = 1+2T(n-1)。这里有证明 http://en.wikipedia.org/wiki/Tower_of_Hanoi 证明 T(n) = 1+2T(n-1) = 2^n-1。因此 T(n-1) = 1+2T((n-1)-1)= 1+2T(n-2) = 2^(n-1) -1。在您的情况下，T(n) = 1 + 2T(n-2) = 2^(n-1) -1。换句话说，在汉诺塔问题中每隔一项减去大约一半的电话。 2^(n-1) - 1 = 2^n/2 - 1 即 O(2^n)。

第二题：这个比较简单。 T(0) = 1 和 T(n) = 1 + T(n-1)。您可以通过多种不同的方式解决这个问题，但其中一种是通过伸缩：

T(n) = 1 + T(n-1)

T(n-1) = 1 + (n-2)

...

T(1) = 1 + T(0)

两边相加...

T(n) + T(n-1)+...+T(1) = 1 + T(n-1) + ... + 1 + T(0) = n + T( n-1)+...+T(0)

减去相似项。

T(n) = n + T(0) = n + 1。所以这是 O(n)。

第三题：与第一题类似。 T(0) = 1，假设我们知道对于 n-1 的值，您可以看到 T(n) = 1 + 2 T(n/2)。注意这里 T(n) = 1 + 2T(n/2) < n + 2T(n/2)。

所以通过递归求解 2T(n/2) + n:

T(n) = 2 T(n/2) + n

T(n/2) = 2 T(n/4) + n/2

所以 T(n) = 4T(n/4) + n + n

T(n/4) = 2T(n/8) + n/4

所以 T(n) = 8T(n/8) n + n + n

...对于正 k，看起来像 T(n) = 2^kT(n/2^k)+kn。

归纳证明。 k = 1: T(n) = 2 T(n/2)+n 给出。这是我们的基本情况。如果 k-1 为真，则显示 k 为真：

T(n) = (2^(k-1))T(n/2^(k-1))+(k-1)n //归纳假设

T(n/2^(k-1)) = 2 T([n/2^(k-1))]/2)+n/2^(k- 1)) //给定递归

= 2T(n/2^k)+n/2^(k-1)

=> T(n) = (2^k)T(n/2^k)+ n + (k-1)n = (2^k)T(n/2^ k) + kn。 k也是如此。

T(n) = 2^kT(n/2^k)+kn，选择合适的正k，如k = ln(n).

T(n) = 2^ln(n) T(n/2^Ln(n)) + nln(n) = nT(1) +nln(n)。

T(1) = 1 因为 Proc 刚刚结束。所以 n(T(1)) + nln(n) = nln(n) + n = O(nln(n))。

不幸的是，对于复杂性，没有一个放之四海而皆准的程序。得具体情况具体分析，找出问题所在。

示例代码计算复杂度的确定

Determination of computational complexity of sample code

complexity-theory