Saya sedikit bingung sambil menghitung kompleksitas waktu kode ini. Bantuan akan sangat dihargai. N = 4 indeks = 1 jumlah = 0 sementara indeks = indeks: j = j // 4 ...

1
heisenbaig 5 April 2021, 19:33

1 menjawab

Jawaban Terbaik
  1. Mulailah dengan menganalisis loop batin. Sejak j = j//4 dalam satu iterasi, dan j beralih dari N ke <=index, loop dalam akan mengambil log(N/index) waktu untuk indeks yang diberikan.
  2. index Bergerak dari 1 ke N.
  3. Menggunakan 1 & amp; 2, Total time = log(N/1) + log(N/2) + log(N/3) ... log(N/N) = log(N!) = O(NlogN)

Jadi kompleksitas waktu keseluruhan adalah O(NlogN).

1
Abhinav Mathur 5 April 2021, 18:08