37-dars: Optimallashtirish

5-darajaOlimpiada — musobaqa mahorati33–40 darslar

HayotdaMusobaqa

Yechimingiz to’g’ri, murakkabligi ham to’g’ri hisoblangan — O(n log n), chegara esa 10⁵. Baribir «vaqt chegarasidan oshdi» keldi. Xato algoritmda emas: siz million marta input() chaqirgansiz va vaqtning yarmi shu yerda ketgan.

Bu darsdan keyin siz

• kirish-chiqishni tez o’qiydigan shablonni yodda saqlaysiz
• bir xil murakkablikdagi yechimlarni konstanta bo’yicha solishtirasiz
• Python chegarasini bilib, qachon C++ kerakligini ayta olasiz

Avval qo’lda

Avval qo‘lda

~6 daqiqa·juftlikda·Kompyuter va sekundomer

Bitta masalani uch xil yozing: 1 dan n gacha yig’indi. Birinchisi oddiy sikl, ikkinchisi sum(range(n + 1)), uchinchisi n * (n + 1) // 2.

n = 10⁶ da uchalasini yurgizib vaqtini yozing. Nisbatlar qanday chiqdi?

Nimani sezishingiz kerak

Uchalasi ham to’g’ri javob berdi. Birinchi va ikkinchi yechimning murakkabligi bir xil — O(n) — lekin vaqt o’nlab barobar farq qildi. Uchinchisi esa umuman aylanmadi.

Kompyuter yopiq. Bu mashq tugamaguncha kod ochilmaydi.

Ikki qator

Olimpiadadagi har Python yechimi shu ikki qatordan boshlanadi. Ular hiyla emas — ular standart.

tez kirish-chiqishNusxalash

1import sys2malumot = sys.stdin.buffer.read().split()3n = int(malumot[0])4a = [int(x) for x in malumot[1 : 1 + n]]5sys.stdout.write(str(sum(a)) + "\n")

▲Bu yerda xato qilishadi

input() har chaqiruvda satr obyektini yasaydi, dekodlaydi va tozalaydi. Million marta chaqirilganda bu ishning o’zi bir necha soniya oladi — algoritmingiz esa hali boshlanmagan. print() ham xuddi shunday: ko’p qatorni bittada sys.stdout.write bilan chiqarish ancha tez.

Konstanta ham ahamiyatli

konstantaconstant factor

Murakkablik bahosida ko’rinmaydigan ko’paytuvchi. O(n) ikki yechimning biri ikkinchisidan 50 barobar sekin bo’lishi mumkin.

?Avval o'ylang: bu kod nima chiqaradi? Ishga tushirishdan oldin yozing.

Bashorat qilingNusxalash

1n = 10002jami = 03for x in range(1, n + 1):4  jami += x5print(jami, sum(range(1, n + 1)), n * (n + 1) // 2)

Sizning bashoratingizTekshirish

Javobni ko'rish

500500 500500 500500

Uchta yechim, bir xil javob. Birinchisi n marta Python amali bajaradi, ikkinchisi bittasini (qolgani C tilida), uchinchisi esa hech qanday sikl ishlatmaydi.

Amaliy qoidalar qisqa. Python siklidan qutulish mumkin bo’lsa — qutuling: sum, max, min, ro’yxat tushunchalari va join hammasi C tilida bajariladi. Ro’yxatga append qilish += bilan satr yig’ishdan ancha tez. Va dict yoki set ga har murojaat narxi bor — uni siklning ichida takrorlamang.

Python chegarasi

Sig‘adimi?

Bir soniyada taxminan 10⁸ oddiy amal bajariladi.

Yechim	n = 100 000	n = 10⁶	n = 10⁷
C++ (taxminan)n	100 000sig‘adi	10⁶sig‘adi	10⁷sig‘adi
Python (taxminan 10–50 barobar sekin)n log n	10⁶sig‘adi	10⁷sig‘adi	10⁸chegarada

Yashil — yechim o‘tadi. Sariq — chegarada, konstanta va til muhim bo‘lib qoladi. Qizil — bu yechim bilan bormaydi, boshqasini qidiring.

Jadval qo’pol, lekin nisbat to’g’ri. Amalda bu shunday ko’rinadi: n ≤ 10⁵ bo’lgan masalalarning deyarli hammasi Python’da o’tadi, n = 10⁶ da ehtiyot bo’lish kerak, n = 10⁷ da esa optimal algoritm ham yetmasligi mumkin.

Xuddi shu yechim ikki tilda quyidagicha ko’rinadi.

yigindi.pyNusxalash

1import sys2malumot = sys.stdin.buffer.read().split()3n = int(malumot[0])4a = [int(x) for x in malumot[1 : 1 + n]]5print(sum(a), max(a))

yigindi.cppNusxalash

1#include <bits/stdc++.h>2using namespace std;3int main() {4  ios::sync_with_stdio(false);5  cin.tie(nullptr);6  int n;7  cin >> n;8  long long jami = 0;9  int eng = 0;10  for (int i = 0; i < n; i++) {11      int x;12      cin >> x;13      jami += x;14      eng = max(eng, x);15  }16  cout << jami << " " << eng << endl;17}

Diqqat qiling: jami uchun long long olingan. int bilan yozilsa million ta milliardgacha son qo’shilganda jimgina buziladi — C++ sahifasidagi eng birinchi ogohlantirish shu haqda edi.

Xotira ham chegara

Vaqt haqida ko’p gapiriladi, xotira haqida kam — lekin u ham nol ball beradi. Python’da ro’yxatdagi har butun son taxminan 28 bayt joy oladi, ya’ni 10⁷ sonli ro’yxat yuzlab megabaytga chiqadi.

Yechim oddiy: kerak bo’lmasa ro’yxat yasamang. Generator ishlating (sum(int(x) for x in ...)), yoki array moduli bilan ishlang.

Sinab ko’r

Vizualda uch yechimning Python darajasidagi amal soni yonma-yon turadi. Farq murakkablikda emas, konstantada.

Konstanta — bir xil murakkablik, boshqa narx

Har qator bitta yechimning Python darajasidagi amal soni.

Bir xil murakkablikdagi yechimlar konstanta tufayli o'nlab barobar farq qilishi mumkin.

Algoritmning har qadami quyidagi ro‘yxatda matn sifatida ham berilgan — vizual faqat shu qadamlarni chizadi, yangi ma’lumot qo‘shmaydi.

1. Bir masala: 1 dan n gacha yig'indi. Uch yechim ham TO'G'RI. Qatorlarda har biri nechta PYTHON amali bajarishi ko'rsatiladi.
2. n = 10^4. Python sikli 10000 marta aylanadi. sum(range(n)) esa bitta chaqiruv: qo'shishlar C tilida bajariladi, ya'ni taxminan o'n barobar arzon. Formula umuman aylanmaydi.
3. n = 10^5. Python sikli 100000 marta aylanadi. sum(range(n)) esa bitta chaqiruv: qo'shishlar C tilida bajariladi, ya'ni taxminan o'n barobar arzon. Formula umuman aylanmaydi.
4. n = 10^6. Python sikli 1000000 marta aylanadi. sum(range(n)) esa bitta chaqiruv: qo'shishlar C tilida bajariladi, ya'ni taxminan o'n barobar arzon. Formula umuman aylanmaydi.
5. Uchalasining murakkabligi bir xil emas: sikl va sum() — O(n), formula — O(1). Lekin muhimi boshqa: BIR XIL murakkablikdagi ikki yechim ham o'nlab barobar farq qilishi mumkin. Konstanta olimpiadada ball keltiradi.

n

10^4010^5110^62

sikl

sum()

formula

Bir masala: 1 dan n gacha yig'indi. Uch yechim ham TO'G'RI. Qatorlarda har biri nechta PYTHON amali bajarishi ko'rsatiladi.

Jami Python amali0

OrqagaO‘ynatishOldinga1/5Qayta boshlash

Xatoni toping

▲Tuzoq — xatoni toping

37 / 40

MasalaYechimim O(n log n), chegara 10⁵. Vaqt chegarasidan oshdi. Nima qilaman?

Taklif qilingan mulohaza

1. 1Murakkablikni qayta hisoblayman — u haqiqatan O(n log n).
2. 2Demak algoritm to‘g‘ri va muammo tilda.
3. 3Yechimni C++ da qaytadan yozaman.
4. 4Endi o‘tishi kerak.

Bu javobning 2-qismi noto'g'ri. Xulosa shoshilinch. Avval KONSTANTANI tekshirish kerak: kirish input() bilan o'qilganmi, chiqish har qatorda alohida print bilan berilganmi, sikl ichida keraksiz ro'yxat yasalmayaptimi. Ko'p holatda shu uchtasini tuzatish yetadi va tilni almashtirish kerak bo'lmaydi.

Javobning qaysi qismi noto'g'ri? Bosib belgilang.

Javobni ko'rsatish

O’zingizni sinang

1input() nega sekin?

Javobni ko'rish

Har chaqiruvda satr obyekti yasaladi, dekodlanadi va tozalanadi. Million marta chaqirilganda bu ish bir necha soniya oladi.

2Bir xil murakkablikdagi ikki yechim qancha farq qilishi mumkin?

Javobni ko'rish

O’nlab barobar. Murakkablik o’sish tezligini beradi, narxni emas — konstanta bahoda ko’rinmaydi.

3Vaqt chegarasidan oshganda birinchi navbatda nima tekshiriladi?

Javobni ko'rish

Kirish-chiqish. Keyin sikl ichidagi keraksiz ish. Til almashtirish — oxirgi chora.

4C++ da yig'indi uchun nega long long olinadi?

Javobni ko'rish

int taxminan 2·10⁹ gacha son saqlaydi. Undan oshsa xato bermay jimgina buziladi.

5Python'da xotira chegarasi qachon muammo bo'ladi?

Javobni ko'rish

10⁷ va undan katta ro’yxatlarda: har butun son taxminan 28 bayt oladi. Yechim — ro’yxat o’rniga generator yoki array moduli.

Masalalar

Masalalar

3 ta

• Weird AlgorithmCSES 1068oson

  Javob juda uzun bo‘ladi. Har sonni alohida print qilmang — ro‘yxatga yig‘ib, join bilan chiqaring.

• Distinct NumbersCSES 1621oson

  Ikki yechimni ham yozing (to‘plam va saralash) va vaqtini solishtiring — farq sezilarli.

• Sum of Three ValuesCSES 1641qiyin

  n ≤ 5000, yechim n². Python‘da bu chegarada konstanta hal qiluvchi bo‘ladi.

Lokal mashq: mashqlar/37-kirish/ — masala matni, testlar va tekshir.py. Avval sekin.py ni o‘zingiz yozing, keyin tayyorini oching.

Topshiriq

Topshiriq — darajangizni tanlang

Asos5–7-sinfMustahkam8–9-sinfChuqur10–11-sinf

Asos · 5–7-sinf — Vizual va aniq ko'rsatmali

1 dan 10⁶ gacha yig’indini uch usulda yozing va vaqtini o’lchang. Uch raqamni jadvalga yozing va nisbatlarni hisoblang.

Mustahkam · 8–9-sinf — Matnli masala, o'zingiz tuzasiz

37-kirish masalasini yeching. sekin.py va tez.py vaqtini 20 000 sonli testda solishtiring, keyin natijani n = 10⁶ uchun bashorat qiling.

Chuqur · 10–11-sinf — Algoritmik, chegara holatlari bilan

O’zingizning shaxsiy chegara jadvalingizni tuzing: bo’sh sikl, qo’shish bilan sikl, ro’yxatga append, dict ga yozish va set da qidirish — har biri uchun 10⁶ amalda qancha vaqt ketadi? Bu jadval keyingi har masalada qaror qabul qilishga yordam beradi.

Darsni belgilash uchun JavaScript kerak. Bu progressni saqlash uchun ishlatiladi — darslikning o'zi JavaScript'siz ham to'liq o'qiladi.

Darsni tugatdim