Hesaplama Zaman Karmaşıklığı Kod

Question

Aşağıdaki snippet'teki zaman karmaşıklığını hesaplama konusunda bir şüphem vardı.

Örnek 1: - için (i = l, n; i> = 1; i = i/2) Printf ("% d", i)

2 Örnek: - için (i = 1, i <, n, 2 i = i * ) Printf ("% d", ı)

I Yukarıda kodları söyleyebilir olacak O (N/2) veya O (gün N) giriş karşı koşmak için zaman karmaşıklığı almak?

Şimdiden teşekkürler.

Answer 1

O (log2 (n)) 'yi alır, sadece this.i = 1' i düşünün, sonra print sonucu 1, o zaman 2,4,8,16 'a kadar 2^x> n, sonra matematik yapın, x> log2 (n), bu nedenle zaman karmaşıklığı O (log2 (n))