Zeit Komplexität: Kontinuierliche Summierung der Ziffern einer Zahl, bis eine einzelne Ziffer Ergebnis

Question

Ich habe eine Nummer N. Halten Sie die Summierung der Ziffern bis eine einzelne Ziffer ergeben. zB 35252 ==> 17 ==> 8 I den folgenden Code geschrieben haben:

int digitSum(int n) 
{ 
    int sum = 0; 
    int digit; 

    while(n) 
    { 
     digit = n%10; 
     n = n/10; 
     sum += digit; 
    } 

    if(sum > 9) 
     return digitSum(sum); 
    else 
     return sum; 
} 

kommend auf die Zeitkomplexität: I den Bereich für die N gegeben werde als 0 < = N < = 10^9 .

Im schlimmsten Fall mit allen 9s, wird die Rekursion geht max zweimal und ich werde O (loglogn)

Im besten Fall mit einstelliger N bekommen, wird die Komplexität seines O (1)

Was wird die durchschnittliche Komplexität sein? Ich meine, was wird die Komplexität sein, wenn N irgendeine Zahl ohne definierten Bereich sein kann.

Answer 1

Zuerst Ihre Analyse ist falsch, die Zeitkomplexität ist nicht O (loglogn) für den ungünstigsten Fall, dann ist es O(logn), mit der folgenden rekursiven Formel:

T(n) = logn + T(log(n) * AVG(digits)) = logn + T(9*logn) 
T(1) = 1 

Jetzt können wir zeigen, dass die oben in O(logn), Induktion mit Induktionsannahme der Verwendung: T(n) <= 2logn

T(n+1) = log(n+1) + T(9logn) <= (i.h) log(n+1) + 2*log(9log(n)) = 
     = log(n+1) + 2log(9) + 2loglog(n) < 2log(n) 

Zeige es Omega(log(n)) ist ziemlich trivial, mit der Beobachtung, daß für alle 0 .

---

die Frage auf der Hand angeht, was die durchschnittliche Zeit Komplexität ist, lassen Sie uns den durchschnittlichen Fall Komplexität bezeichnen mit G(n), und lassen Sie uns n annehmen gleichmäßig verteilt ist (wenn es nicht ist -, dass die Analyse wird sich ändern, und das Ergebnis könnte anders sein).

G(N) = lim{N->infinity} sum{i=1 to N} T(n)/N = 
    = lim{N->infinity} T(1)/N + T(2)/N + ... + T(N)/N 
    = lim{N->infinity} 1/N (T(1) + T(2) + ... + T(N)) 
    < lim{N->infinity} 1/N (2log(1) + 2log(2) + ... + 2log(N)) 
    = lim{N->inifnity} 2/N (log(1) + ... + log(N)) 
    = lim{N->inifnity} 2/N (log(1 * 2 * ... * N)) 
    = lim{N->infinity} 2/N log(N!) 
    = lim{N->infinity} 2/N * CONST * NlogN = 2*CONST * logN 

So können wir G(N) schließen auch in O(logN), so dass die durchschnittliche Fallanalyse ist in N noch logarithmisch.

Answer 2

Bekannte Lösung ist n% 9 + (n% 9 == 0? 9: 0).