Karmaşıklık hakkında algoritma tasarımında bir sorum var. Bu soru, bir parça kodu verilir ve bu kod karmaşıklığını hesaplamak gerekir. Pseudo-kod:

for(i=1;i<=n;i  ){
    j=i
    do{
        k=j;
        j = j / 2;
    }while(k is even);
}

Bazı sayılar için bu algoritma çalıştım. ve farklı sonuçlar aldık. örneğin n = 6 Bu algoritma çıktısı aşağıdaki gibidir

i = 1 -> executes 1 time
i = 2 -> executes 2 times
i = 3 -> executes 1 time
i = 4 -> executes 3 times
i = 5 -> executes 1 time
i = 6 -> executes 2 times

Düzenli bir tema yok, bu nasıl hesaplamak gerekir?

Üst diğer cevaplar verdiği bağlı aslında çok yüksek. Bu algoritma daha sıkı bir üst sınır daha bir O(n*log n) (n) çalışma zamanı vardır.

Kanıt: iç döngü yapacak nasıl sayayım.

Dış döngü n kez çalışır. İç döngü en az bir kere bunların her biri için çalışır.

• Hatta i, iç döngü en az iki kere çalışır. Bu n/2 katı olur.
• i 4, iç döngü ile bölünebilen için çalışan en az üç kez. Bu n/4 kat olur.
• i 8, iç döngü ile bölünebilen için çalışan en az dört kez. Bu n/8 katı olur.
• ...

İç döngü çalışır kez toplam miktar:

n   n/2   n/4   n/8   n/16   ... <= 2n

İç döngü tekrar miktarı n ve Θ. 14*, yani* (n) arasında.