Bu işlev için algoritma karmaşıklığı

Question

def mystery(L): 

sum1 = 0 
sum2 = 0 
bound = 1 
while bound <= len(L): 
    i = 0 
    while i < bound: 
     j = 0 
     while j < len(L): 
      if L[j] > L[i]: 
       sum1 = sum1 + L[j] 
      j = j + 2 
     j = 1 
     while j < len(L): 
      sum2 = sum2 + L[j] 
      j = j*2 
     i = i + 1 

    bound = bound * 2 
return sum1 + sum2 

Bu işlevin karmaşıklığını bulmakta zorlanıyorum. Ben i döngü var ve ne yapacağımı bilmiyorum.

Answer 1

Orta düzey while döngüsünün kaç kez çalıştığını belirlemek biraz zor. Dış döngü bound her geçişte iki kat artar (len(L)'a kadar), yani i döngüsü O(log(N)) geçişleri için O(log(N)) geçişleri için (Nlen(L) olduğu) geçişler için çalışır. Zor olan kısım, her geçişte değiştikleri için bound değerlerini nasıl ekleyeceğimizdir.

Toplamı belirlemenin en kolay yolu, döngüden çıkmadan hemen önce en büyük bound ile başlamaktır. İlk olarak, N (len(L)) değerinin 2 gücü olduğunu varsayalım. Son olarak bound değeri N'a eşit olacaktır. Bir sonraki daha küçük olan (en sonuncu yinelemede kullanılan) N/2 ve bundan sonraki N/4 olacaktır. Onların toplamı olacaktır:

N + N/2 + N/4 + N/8 + ... + 1 

her dönemden N çarpanlarına, biz alırsınız:

N*(1 + 1/2 + 1/4 + 1/8 + ... + 1/N) 

Sen parantez içinde toplamını tanımalı, basit bir geometrik dizi var (toplamı matematik ve analizde sıklıkla ortaya çıkan 1/2'un güçlerinin). Toplam sonsuza kadar devam ederse, tam olarak 2'a eklenir. Biraz erken ayrıldığımızdan beri, son terime eşit bir miktarla ikiden az olacak (1/N). Yine de N çarpıldığını, biz 2*N - 1 kez yürütülüyor olarak her şeyi almak, böylece döngü, O(N)

N tam 2 'lik bir güç değildir, aynı Big-O ciltli eserler olduğu değerler beri Yukarıdaki analize eklenenler, döngüde göreceğimiz gerçek bound değerlerinden birinin üst sınırı olarak hizmet edecektir.

Yani, i döngü, O(N) kez çalışır.