Algoritmlar murakkabligini ifodalash uchun Katta O belgisi (Big O notation) ishlatiladi. Bu belgi algoritmning eng yomon holatda nechta qadam bajarishini ko'rsatadi.
O(n) — chiziqli murakkablik degani. n — kirish ma'lumotlari soni. Agar n ta elementli ro'yxatni bitta sikl bilan aylanib chiqsak, jami n ta qadam bajarilad va shu algoritmning murakkabligi O(n) bo'ladi.
Masalan, ro'yxatdan son qidirish O(n) murakkablikka ega:
Big O har doim eng yomon holatni ko'rsatadi. Bu yerda 8 ta element bor — izlangan son eng oxirida bo'lsa, 8 ta qadam ketadi. 1000 ta element bo'lsa, eng yomon holatda 1000 ta qadam.
Keling, bu o'sishni grafikda ko'raylik — n oshgan sari qadamlar soni qanday o'sadi:
Ko'rdingizmi? Grafik to'g'ri chiziq hosil qiladi — shuning uchun bu chiziqli murakkablik deyiladi. n 2 baravar oshsa, qadamlar ham 2 baravar oshadi.
Muhim qoidalar:
O(n)O(n) + O(n) = O(2n), lekin Big O da konstantalar tushirib qoldiriladi → O(n). Ya'ni O(n) va O(2n) algoritmik nuqtai nazaridan bir xil hisoblanadi.