Binärwert-Algorithmus zählen || beweis groß oh

Question

Ist das große oh (Log n)? wie kann ich es beweisen durch Summierung mit

//Input: A positive decimal integer n 
    //Output: The number of binary digits in n’s binary representation 
    count ← 1 
while n > 1 do 
count ← count + 1 
n ← ⌊n/2⌋ 
return count 

Answer 1

Big Oh Komplexität leicht durch Zählen Anzahl, wie oft die while-Schleife läuft wie die Vorgänge innerhalb while-Schleife nehmen konstant time.In diesen Fall N variiert as- berechnet werden kann

N,N/2,N/4,N/16.... ,1 

Gerade Zählen Anzahl von Ausdrücken in oben Serie gibt mir einige Male Schleife runs.So,

N/2^p=1  (p is number of times loop runs) 

Diese p = log N gibt somit Komplexität 0 (logN)

Answer 2

Überprüfen Sie einfach den zurückgegebenen Wert count. Wie es näher an logN wäre, können Sie angeben, dass das TC log(N) ist.

Denken Sie einfach umgekehrte Weg (mathematisch):

1 -> 2 -> 4 -> 8 -> ... N (xth value considering 0-indexing system) 
2^x = N 
x = logN 

Answer 3

Man muss bedenken, dass eine größere Anzahl mehr Speicher und für jede Operation mehr Verarbeitung übernehmen. Hinweis: Zeitkomplexität interessiert nur, was bei den größten Werten passiert, nicht bei den kleineren. Die Anzahl der Iterationen ist log2(n). Die Kosten für die n > 0 und n = n/2 sind jedoch proportional zur Größe der ganzen Zahl. d.h. 128-Bit-Kosten zweimal 64-Bit und 1024-Bit sind 16-mal größer. Die Kosten für jede Operation sind also log(m), wobei m der maximal vorzeichenlose Wert ist, den die Anzahl der Bits speichert. Wenn Sie davon ausgehen, dass es sich um feste Fehlerbits handelt, z.B. nicht mehr als 64-Bit bedeutet dies die Kosten O(log(n) * log(n)) oder O(log(n)^2)

Wenn Sie Java BigInteger verwendet, ist, was die Zeit Komplexität wäre.

Answer 4

Die n wird wie folgt reduziert:

n + n/2 + n/4 + n/8 + .... + 8 + 4 + 2 + 1 

Die Summe der obigen Reihe ist 2^(log(n)) - 1.

Nun zu der obigen Frage kommen. Die Anzahl der Male, die die Schleife ausgeführt wird, ist die Anzahl der Elemente, die in der obigen Reihe erscheinen = Zeitkomplexität des Algorithmus.

Die Anzahl der Elemente in der obigen Reihe ist logn. Die Zeitkomplexität des Algorithmus ist also O(logn).

Example: 
n = 8; the corresponding series: 
8 + 4 + 2 + 1 = 15(2^4 - 1) ~ 2^4 ~ 2^logn 
Here, number of items in series = 4 

therefore, 
time complexity = O(number of iteration) 
       = O(number of elements in series) 
       = O(logn)