Wie berechnet man Algorithmus Zeit komplexen

Question

Ich versuche, zwei große Ganzzahl mit Karatsuba Algorithmus zu multiplizieren. Ich weiß, dass O(n) ist Zeit Komplexität und T(n) ist ungünstigsten Zeit Komplexität.

Kann jemand bitte erklären, warum:

T(n) = 4T(n/2) + O(n) is O(n^2) 

Und

T(n) = 3T(n/2) + O(n) is O(n^1.59) 

Answer 1

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

zum Master-Satz nach:

T(n) is O(n^log_2(4)) = O(n^2) 

und

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

ist

T(n) = O(log_2(3)) ~ O(n^1,5849) 

, so dass Sie es zu 1.590 abrunden können.