Big O notation

Big O o'zi nima?

Tasavvur qiling siz qandaydir yangi algoritm yaratingiz. Siz uni yaxshi yoki yomon algoritm ekanligini qanday bilasiz? Shubhasiz, algoritm o‘z ishini to‘g‘ri bajaryapti yo‘qmi shuni tekshirasiz, lekin siz yozgan algoritm vazifani to‘g‘ri bajardi degani bu zo‘r algoritm degani emas.

Algoritm yaxshi yoki yomonligini bilish uchun 2ta narsaga e'tibor beriladi:

• time complexity (algoritm vazifani bajarish uchun qancha vaqt sarfladi)
• space complexity (algoritm vazifani bajarish uchun qancha joy egalladi)

Big O - algoritmning samaradorligini aniqlash uchun ishlatiladigan metrika.

Big O turlari

O(1)

Bu eng zo‘r natija ya’ni inputlar sonidan qat’iy nazar bu algoritm o‘z ishini tugatish uchun O1 vaqt sarflaydi, ya’ni 1 ta operatsiyani o'zi yetarli.

O(n)

Bu holat uchun linear search yaxshi misol bo‘la oladi. Tasavvur qiling bizda shunaqa integerlardan tashkil topgan list bor:

qaysidir 1 ta soni topmoqchi bo‘lsak, arrayni boshidan oxirigacha iteratsiya qilishga to‘g‘ri keladi, shu holatda algoritm tezligi O(n) bo‘ladi. N bu listni uzunligi.

Shu yerda 1 ta qiziq holat bor, aytaylik qidirayotgan son listni boshida turibdi, misol uchun tepadagi holatda 1, bu holatda algoritm o‘zini ishini yakunlash uchun 1 operatsiya yetarli deyishingiz mumkin, lekin Big O eng yomon holat bilan o'lchanadi.

O(n²)

Bunday holatni asosan ichma ich loop da uchratasiz, chunki bunday holatda algoritm tezligi listning uzunligining kvadratiga teng bo‘ladi.

O(logn)

Bu tezlik O(n) dan yaxshiroq. O(logn) uchun eng zo'r misol bu Binary Search.

Binary Search tezligi O(logn) ekanligiga sabab har bir sikldan keyin listning yarmi kesib tashlanadi.

O(n log n)

O(n log n) - bu O(On) dan sekingroq lekin O(n²) dan tezroq. Bunga QuickSort va MergeSort misol bo'la oladi.

Bu chizma algoritm samaradorligini tezda baholash va to‘g‘ri tanlov qilishingizga yordam beradi.

English version:

English version of the article is here.

Ali Ismoilov, 29.01.24

Italiya, Messina