Saya terjebak pada notasi O Besar ini tentang bagaimana seharusnya menjadi O(n^3). Di mana proses berpikir saya salah?

Saya tahu bahwa perulangan for bersarang adalah O(n^2) dan perulangan while mungkin merupakan fungsi O(nlogn) karena perulangan for adalah fungsi O(n) dan nilai perulangan while dikalikan dua yang membuatnya menjadi O(logn). Karena itu, jawabannya dinyatakan sebagai O(n^3) dan saya bingung bagaimana ini terjadi kecuali bagian rekursif dari fungsi ada hubungannya dengan itu?

def do_stuff2(n, x=1.23):
    if n <= 0:
        return 0
    val = 1
    for i in range(n//2):
        for j in range(n//4):
            x += 2*x + j/2 + i*1.2
    while val <= n:
        for i in range(n):
            x += val**2 + i//2
        val *= 2
    x += do_stuff2(n - 1, x/2)
    return x

Saya percaya bahwa x tidak mempengaruhi notasi o besar karena merupakan konstanta karena tidak digunakan dalam memutuskan berapa kali salah satu loop loop.

Jadi sekali lagi, saya mengharapkan output dari fungsi menjadi O(n^2), tetapi output sebenarnya adalah O(n^3)

1
Krystalism 29 Mei 2019, 13:39

2 jawaban

Jawaban Terbaik

Fungsi Anda memiliki dua loop for bersarang, yaitu O(n^2):

for i in range(n//2):
    for j in range(n//4):
        x += 2*x + j/2 + i*1.2

Namun di atas itu, fungsi do_stuff2() Anda mengambil argumen n dan memanggil dirinya sendiri hingga n <= 0, artinya itu satu lagi O(n).

2
Markus Meskanen 29 Mei 2019, 10:42

Lihat baris terakhir dari fungsi: x += do_stuff2(n - 1, x/2) ini adalah panggilan rekursif. anda memiliki n panggilan rekursif, masing-masing adalah O(N^2), total O(N^3)

0
S.A 29 Mei 2019, 10:47