4-dars: Murakkablik intuitsiyasi

1-darajaBronza — algoritmik fikrlash1–8 darslar

HayotdaMusobaqa

Ikki o’quvchi bir xil masalani yechdi va ikkalasining ham javobi to’g’ri. Birinchisining programmasi 0,2 soniyada tugadi, ikkinchisiniki esa uch soatdan keyin ham ishlab turibdi. Ikkinchisi xato qilmagan — u shunchaki chegaraga qaramagan.

Bu darsdan keyin siz

• shartdagi chegara raqamiga qarab qaysi yechim yetishini oldindan aytasiz
• 10⁸ qoidasini har masalada ishlatasiz
• «to’g’ri» va «yetarlicha tez» ikki boshqa narsa ekanini bilasiz

Avval qo’lda

Avval qo‘lda

~5 daqiqa·yakka·Qog'oz, qalam va kalkulyator

Kompyuter bir soniyada taxminan 100 million oddiy amal bajaradi deb oling. Endi uchta savolga javobni qog’ozga yozing.

Birinchi: n = 1000 da n² nechta amal? Ikkinchi: n = 1000000 da n² nechta amal? Uchinchi: shu ikkinchi son necha soniya, va bu necha soat bo’ladi?

Nimani sezishingiz kerak

Birinchi javob — 1 million, ya’ni yuzdan bir soniya. Uchinchisi esa 10¹² amal, ya’ni 10 000 soniya — deyarli uch soat. Ikki savol orasida n faqat ming marta o’sdi, vaqt esa million marta.

Kompyuter yopiq. Bu mashq tugamaguncha kod ochilmaydi.

Sekin yechim

Masala oddiy: sinfda nechta juftlik bir kunda tug’ilgan? Birinchi fikr — har juftlikni ko’rib chiqish.

sekin.pyNusxalash

1kunlar = [14, 3, 27, 9, 3, 14]2soni = 03for i in range(len(kunlar)):4  for j in range(i + 1, len(kunlar)):5      if kunlar[i] == kunlar[j]:6          soni += 17print(soni)

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

Bashorat qilingNusxalash

1kunlar = [14, 3, 27, 9, 3, 14]2soni = 03for i in range(len(kunlar)):4  for j in range(i + 1, len(kunlar)):5      if kunlar[i] == kunlar[j]:6          soni += 17print(soni)

Sizning bashoratingizTekshirish

Javobni ko'rish

2

Ikkita juftlik: ikkita 14 va ikkita 3. Olti kishilik sinf uchun jami 15 ta taqqoslash bo'ldi.

Nega sekin

Olti kishi uchun 15 ta taqqoslash — hech gap emas. Lekin masalaning chegarasi n ≤ 200000 deb yozilgan. Shu raqamni qo’yib ko’ramiz.

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

Bashorat qilingNusxalash

1n = 2000002print("har juftni ko'rish:", n * n // 2)3print("bir marta yurish:", n)

Sizning bashoratingizTekshirish

Javobni ko'rish

har juftni ko'rish: 20000000000
bir marta yurish: 200000

20 milliard — bu 10⁸ chegarasidan 200 marta katta. Programma to'g'ri, lekin javobni hech kim kutib o'tirmaydi.

Sig‘adimi?

Bir soniyada taxminan 10⁸ oddiy amal bajariladi.

Yechim	n = 1 000	n = 5 000	n = 200 000
Har juftni ko‘rishn^2	10⁶sig‘adi	10⁷sig‘adi	10¹⁰sig‘maydi
Saralab yurishn log n	9 966sig‘adi	61 439sig‘adi	10⁶sig‘adi
Bir marta yurishn	1 000sig‘adi	5 000sig‘adi	200 000sig‘adi

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

10⁸ qoidasi

chegaraconstraint

Shartda yozilgan «n shundan katta bo’lmaydi» degan raqam. U bezak emas — aynan shu raqam qaysi yechim qabul qilinishini aytadi.

Bir soniyada taxminan 10⁸ oddiy amal bajariladi. Demak yechim tanlashdan oldin bitta savolga javob berish kerak: mening yechimim shu chegarada nechta amal qiladi va u 10⁸ dan oshadimi?

Javobni yodlash shart emas, jadval yetadi:

Chegara	Sig’adigan yechim	Nomi
n ≤ 20	2ⁿ	barcha ichki to’plamlar
n ≤ 500	n³	uchta ichma-ich sikl
n ≤ 5000	n²	har juftni ko’rish
n ≤ 10⁶	n log n	saralash, ikkilik qidiruv
n ≤ 10⁸	n	bir marta yurish

◆Asosiy g'oya

Jadvalni teskari o’qish kerak: avval chegaraga qaraysiz, keyin yechim tanlaysiz. Yechim yozib bo’lgandan keyin chegaraga qarash — vaqtni ikki marta sarflash demakdir.

Tez yechim

Juftliklarni sanash uchun ularni ko’rish shart emas. Bir kunda nechta o’quvchi tug’ilganini bilsak, o’sha kundagi juftliklar sonini formula bilan chiqarish mumkin: k kishidan k · (k−1) / 2 juftlik tuziladi.

tez.pyNusxalash

1from collections import Counter2kunlar = [14, 3, 27, 9, 3, 14]3soni = 04for k in Counter(kunlar).values():5  soni += k * (k - 1) // 26print(soni)

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

Bashorat qilingNusxalash

1from collections import Counter2kunlar = [14, 3, 27, 9, 3, 14]3soni = 04for k in Counter(kunlar).values():5  soni += k * (k - 1) // 26print(soni)

Sizning bashoratingizTekshirish

Javobni ko'rish

2

Ikkita 14 dan bitta juftlik, ikkita 3 dan bitta juftlik. Yolg'iz kunlar nol beradi, chunki bitta kishidan juftlik tuzilmaydi.

Ikkita ichma-ich sikl bitta siklga aylandi va 20 milliard amal 200 mingga tushdi — yuz ming marta kam.

Sinab ko’r

Vizualda ikkala yechim yonma-yon ishlaydi. Pastdagi amal hisoblagichiga qarab turing: butun darsning mazmuni o’sha raqamning o’sish tezligida.

Bir masala, ikki yechim — amal soni

Pastdagi «amal soni» qatoriga qarab turing: farq shu yerda ko'rinadi.

Birinchi yechim har juftni tekshiradi, ikkinchisi ro'yxat bo'ylab bir marta yuradi. Javob bir xil, amal soni har xil.

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

1. Savol: ro'yxatda takrorlangan son bormi? Ikki yechimni yonma-yon ko'ramiz.
2. 0 va 1: 5 va 8 — har xil.
3. 0 va 2: 5 va 1 — har xil.
4. 0 va 3: 5 va 9 — har xil.
5. 0 va 4: 5 va 3 — har xil.
6. 0 va 5: 5 va 8 — har xil.
7. 1 va 2: 8 va 1 — har xil.
8. 1 va 3: 8 va 9 — har xil.
9. 1 va 4: 8 va 3 — har xil.
10. 1 va 5: 8 = 8 — takror topildi. 9 ta taqqoslashdan keyin.
11. 5 yangi — ko'rilganlar to'plamiga qo'shildi.
12. 8 yangi — ko'rilganlar to'plamiga qo'shildi.
13. 1 yangi — ko'rilganlar to'plamiga qo'shildi.
14. 9 yangi — ko'rilganlar to'plamiga qo'shildi.
15. 3 yangi — ko'rilganlar to'plamiga qo'shildi.
16. 8 ko'rilganlar ichida bor edi — takror topildi. Bor-yo'g'i 6 qadam.
17. Bir xil javob: 9 amal va 6 amal. n = 6 da farq kichik. Endi n = 1000 ni tasavvur qiling.

har juft

508112933485

bir marta

581938

ko'rilganlar

amal soni

sekin0tez0

Savol: ro'yxatda takrorlangan son bormi? Ikki yechimni yonma-yon ko'ramiz.

Amal0

OrqagaO‘ynatishOldinga1/17Qayta boshlash

Xatoni toping

▲Tuzoq — xatoni toping

4 / 40

MasalaShartda n ≤ 100000. Har juftni ko'radigan yechim yozsam bo'ladimi?

Taklif qilingan mulohaza

1. 1n = 100000, demak juftliklar soni taxminan n²/2.
2. 2Bu 5 · 10⁹ ta amal bo‘ladi.
3. 3Kompyuter bir soniyada 10⁸ amal bajaradi, ya‘ni bu 50 soniya.
4. 4Vaqt chegarasi odatda 1 soniya, demak bu yechim o‘tmaydi.

Bu javobning 3-qismi noto'g'ri. Bo'lish to'g'ri bajarilgan, lekin 10⁸ raqami Python uchun emas. Python bir soniyada taxminan 10⁷ oddiy amal bajaradi, ya'ni haqiqiy vaqt 50 emas, 500 soniyaga yaqin. Xulosa tasodifan to'g'ri chiqdi — mulohaza esa yo'q.

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

Javobni ko'rsatish

O’zingizni sinang

1Shartda n ≤ 18 yozilgan. Qanday yechim o'ylash mumkin?

Javobni ko'rish

2ⁿ yechim — barcha ichki to’plamlarni ko’rib chiqish. 2¹⁸ = 262 144, bu juda kichik son. Shunchalik kichik chegara odatda ochiq ishora bo’ladi: to’liq izlash kutilmoqda.

2n ikki barobar oshsa, n² yechim necha barobar sekinlashadi?

Javobni ko'rish

To’rt barobar. Shuning uchun n² yechimlar «birdan» sekinlashib qolgandek tuyuladi: kirish biroz o’sadi, vaqt esa sakraydi.

3«To'g'ri yechim» bilan «o'tadigan yechim» bir narsami?

Javobni ko'rish

Yo’q. To’g’ri yechim doim to’g’ri javob beradi, o’tadigan yechim esa buning ustiga vaqt va xotira chegarasiga ham sig’adi. Olimpiadada faqat ikkinchisi ball keltiradi.

4n ≤ 10⁶ da n log n yechim nechta amal qiladi?

Javobni ko'rish

log₂(10⁶) taxminan 20, demak 2 · 10⁷ atrofida. Bu 10⁸ chegarasidan past, ya’ni sig’adi. Shu sababli saralashga asoslangan yechimlar bunday chegarada eng ko’p uchraydi.

5Kod yozishdan oldin qaysi ikki raqamni yozib olish kerak?

Javobni ko'rish

Chegarani (n maksimal qiymati) va o’z yechimingiz shu chegarada qiladigan amal sonini. Ikkinchi raqam 10⁸ dan katta bo’lsa, kod yozishdan avval boshqa yechim izlanadi.

Masalalar

Masalalar

3 ta

• Distinct NumbersCSES 1621oson

  n ≤ 2·10⁵. Har juftni ko‘rish sig‘maydi — chegara buni ochiq aytib turibdi.

• Sum of Two ValuesCSES 1640o'rta

  Avval n² yechimni yozing va kichik testda tekshiring, keyingina tezlashtiring.

• Bear and Big BrotherCodeforces 791Aoson

  Necha marta aylanishini oldindan baholang — sikl albatta tugaydimi?

Lokal mashq: mashqlar/04-takror/ — 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

Jadvalni daftaringizga ko’chirib oling va yodlamang — uni har masalada ochib qarang. Keyin uchta chegara yozing (n ≤ 15, n ≤ 4000, n ≤ 500000) va har biriga qaysi yechim sig’ishini belgilang.

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

04-takror masalasini yeching. Avval sekin.py ni yozing va uni n = 200000 li test bilan yurgizib ko’ring — necha soniya ketdi? Keyin tez.py ni yozing va ikkalasining vaqtini yonma-yon yozing.

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

Python’da 10⁷ amal haqiqatan qancha vaqt olishini o’lchang: bo’sh sikl, qo’shish bilan sikl va ro’yxatga yozish bilan sikl. Uch raqamni taqqoslang va o’zingiz uchun shaxsiy chegara raqamini aniqlang.

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

Darsni tugatdim