O(n²) — Kvadratik murakkablik

Ba'zi algoritmlar ichma-ich sikllardan (nested loops) iborat bo'ladi. Bu holda qadamlar soni n × n = n² ga teng bo'ladi.

Keling, 2 ta ichma-ich sikllardan iborat algoritmni kodda kuzataylik:

n=4 bo'lganda natija 16 qadam (4 × 4). Agar n=10 bo'lsa — 100 qadam, n=100 bo'lsa — 10,000 qadam!

Endi O(n) va O(n²) ni grafikda solishtiraylik:

Ko'rdingizmi? O(n²) algoritm bajaradigan qadamlar soni O(n) algoritmga nisbatan ancha tez o'sadi. n katta bo'lgan sari farq keskin oshadi — shuning uchun ko'p miqdordagi ma'lumotlar bilan ishlashda O(n²) algoritmlar juda sekin bo'ladi.

Muhim qoidalar:

• 2 ta ichma-ich sikl → O(n²) murakkablik
• Juda katta n uchun O(n²) juda sekin ishlaydi
• O(n) va O(n²) o'rtasidagi farq n oshganda keskin ortadi