Определение вычислительной сложности образца кода

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). Проблему можно решить множество различных способов, но один из них с помощью телескопической:

Т (п) = 1 + Т (п-1)

Т (п-1) = 1 + (N-2)

...

Т (1) = 1 + T (0)

Сложение обеих сторон ...

Т (п) + Т (п-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).

Так решить для 2Т (п/2) + п с раскатывания рецидива:

T (N) = 2 T (N/2) + п

Т (п/2) = 2 Т (п/4) + п/2

Таким образом, Т (п) = 4T (п/4) + п + п

Т (п/4) = 2T (п/8) + п/4

Таким образом, T (n) = 8T (n/8) n + n + n

... Похоже, что T (n) = 2^kT (n/2^k) + kn для положительных k.

Докажите это по индукции. k = 1: T (n) = 2 T (n/2) + n, которое было задано. Это наш базовый случай. Если значение true для k-1, показать true для 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)) // При рецидивы

= 2Т (п/2^к) + п/2^(к-1)

=> Т (п) = (2^к) Т (п/2^к) + 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)).

К сожалению, процедуры не подходят для любой сложности. Вы должны принять его в каждом конкретном случае и выяснить проблему.