1. Giriş
Təsəvvür edin ki, proqram yazmısınız: düzgün cavabı çıxardır, kompilyator səhv vermir və demək olar ki, qeyd etməyə hazırsınız. Amma sonra kimsə girişdə üç ədəd əvəzinə üç milyon gətirir. Bu məqamda aydın olur ki, «işləyir» və «sürətlə işləyir» — iki fərqli məfhumdur.
Çətinlik (Big‑O) mikrosaniyələr və ya «mənim noutbuk güclüdür» barədə deyil; bu, giriş ölçüsü artdıqca əməliyyatların necə artdığı haqqındadır.
Təhsil müddətində ən vacib şey təhlükəli yerləri görməyi öyrənməkdir: məsələn, kiçik nisbətlərdə şirin görünən iki daxili dövr böyük girişdə «fanat nədən hava alır, turbina kimi oxuyur» vəziyyətinə çevrilə bilər.
Nə sayırıq və N nə deməkdir
O(…) haqqında danışmaq üçün bizim N parametri lazımdır — girişin ölçüsü. «Ölçü» sözü burada mütləq bayt və ya meqabayt demək deyil; daha çox «neçə element», «neçə ədəd», «neçə sətir», «hansı rəqəmə qədər gedirik» mənasını verir.
Zamanı stopqramla ölçməyəcəyik — bunun əvəzinə «tipik əməliyyat»ın (məsələn, dövrün bədəni) neçə dəfə yerinə yetirildiyini sayacağıq. Bu cür sayma xamdır, amma eyni ideyanın böyük girişdə niyə fərqli davrandığını göstərmək üçün əladır.
Vacib: biz «1342 əməliyyat» kimi dəqiq formul axtarmırıq. Biz böyümə xassəsini axtarırıq. Əgər N 10 dəfə artdıqda əməliyyatların sayı təxminən 10 dəfə artırsa — bu bir növ böyümədir. Əgər təxminən 100 dəfə artırsa — tamamilə fərqli xassədir.
2. Bir dövr: O(N)
Bir dövr, hansı ki 0-dan N-ə (və ya 1-dən N-ə) gedirsə, adətən xətti böyümə verir: «təxminən N təkrar». Buna O(N) deyilir. Bu o deməkdir: əgər N 10 dəfə artarsa, iş də təxminən 10 dəfə artar. Dəqiq 9.7 və ya 10.3 deyil — indi bizim marağımız xam şəkildir.
Gəlin sözə inanmayıb kiçik «əməliyyat sayğacı» edək — dövrün bədənində artıracağımız dəyişən. Bu vaxt ölçmə vaxtı deyil, amma dövrün neçə dəfə həqiqətən işlədiyini görməyin dürüst üsuludur.
Nümunə: for bədənin neçə dəfə icra olunduğunu «saymaq»
#include <iostream>
int main() {
int n = 0;
std::cin >> n;
int ops = 0;
for (int i = 0; i < n; i = i + 1) {
ops = ops + 1; // bir əməliyyatı sayırıq
}
std::cout << ops << '\n'; // n=5 olduqda 5 olacaq
}
Burada ops sonunda təxminən n-ə bərabər olacaq. Əgər n = 1000, nəticə 1000 olacaq. Əgər n = 1'000'000, nəticə milyon olacaq. Xətti, dürüst, sürprizsiz.
Mini-cədvəl ölçünü hiss etmək üçün
Hələ riyaziyyat olmadan — sadəcə «rəqəm hissi»:
| N | Təxminən bədənin icra sayı (O(N)) |
|---|---|
| 10 | 10 |
| 100 | 100 |
| 1000 | 1000 |
| 10 000 | 10 000 |
Bu məqamda adətən inam yaranır: «yaxşı, bir dövr qorxulu deyil». Və çox vaxt bu doğrudur. Məsələlər başlayır ki, biz təkrarlama saylarını vurmağa başlayırıq.
3. Daxili dövrlər: O(N²)
Ən vacib məqam: bir dövr başqa dövrün içində olduqda, daxili hər addımda xaricinin hər addımında işləyir. Əgər xarici N addım edirsə və hər addımda daxili də N addım edirsə — təxminən N · N, yəni N² alınır.
Bu niyə vacibdir: əgər N 10 dəfə artarsa, N² təxminən 100 dəfə artar. Giriş bir qədər artdı — proqram birdən çox yavaşlaşdı.
Nümunə: cütləri sayırıq (i, j)
#include <iostream>
int main() {
int n = 0;
std::cin >> n;
long long ops = 0;
for (int i = 0; i < n; i = i + 1) {
for (int j = 0; j < n; j = j + 1) {
ops = ops + 1;
}
}
std::cout << ops << '\n'; // n=3 olduqda 9 olacaq
}
Əgər n = 3, nəticə 9 alınır. Əgər n = 10, nəticə 100 olacaq. Əgər n = 1000, artıq 1 000 000 olacaq. Burada böyümə daha kəskin hiss olunur.
Vizual sxem: niyə vurma əməliyyatı alınır
Ağlımız bu işi sehr kimi dayandırmasın deyə, belə təsəvvür edə bilərsiniz:
İdea sadədir: «daxili dövr hər i üçün tam işləyir». Buna görə vurma əməliyyatı alınır.
Kvadratik böyümə üçün mini-cədvəl
| N | Təxminən bədənin icra sayı (O(N²)) |
|---|---|
| 10 | 100 |
| 100 | 10 000 |
| 1000 | 1 000 000 |
| 10 000 | 100 000 000 |
Və artıq 10 000-da zarafat vaxtı deyil: yüz milyon təkrar — bu yaxşı kompüterdə belə nəzərə çarpan ola bilər, təhsil platformasında və ya zəif mühitdə isə daha da çox.
Daxili dövr N-ə qədər olmaya bilər: «üçbucaq», amma yenə də O(N²)
Bəzən tələbələr belə kod görürlər: for (j = 0; j < i; ++j) və ümid edirlər ki, daxili dövr «qısa» olduğuna görə çətinlik artıq kvadratik deyil. Əslində çox vaxt bu hələ də kvadratik böyümədir, sadəcə əmsal kiçik olur.
Daxili dövr əvvəlcə qısa, sonra getdikcə uzun olur — və cəmi təxminən «kvadratın yarısı» toplanır. Biz indi düsturlar ilə sübut etməyəcəyik, amma intuisiyada bu belə hiss olunur: böyük N üçün daxili iş hələ də təxminən N² kimi artır.
#include <iostream>
int main() {
int n = 0;
std::cin >> n;
long long ops = 0;
for (int i = 0; i < n; i = i + 1) {
for (int j = 0; j < i; j = j + 1) {
ops = ops + 1;
}
}
std::cout << ops << '\n'; // n=4 olduqda 6 olacaq
}
n = 4 olduqda daxili dövr 0 + 1 + 2 + 3 = 6 addım edir. n = 5 olduqda nəticə 10 olacaq. Bu təxminən «kvadrat» kimi artır, sadəcə tam kvadrat yox, «üçbucaq» şəklində.
4. Konstantlar, bir neçə keçid və break
O(…) dedikdə, biz adətən kiçik detalları nəzərə almırıq: «+ 5 əməliyyat», «+ 2» və ya hətta «2-yə vurmaq». Bunun səbəbi riyaziyyatçıların pisliyi deyil — böyük N üçün bu əlavələr böyümə xassəsini dəyişmir.
Məsələn, ardıcıl iki dövr hər biri N iterasiya edirsə — bu təxminən 2N əməliyyat deməkdir, amma böyümə hələ də xətti qalır: N 10 dəfə artsa, 2N də 10 dəfə artacaq.
Praktik detal: C++ standart kitabxanasının sənədlərində çətinlik adətən məhz böyümə şəklində (məsələn, N·logN) yazılır, çünki əsas olan sıra, «+/- 17 əməliyyat» deyil.
İki müstəqil xətti dövr: hələ də O(N)
#include <iostream>
int main() {
int n = 0;
std::cin >> n;
int ops = 0;
for (int i = 0; i < n; i = i + 1) ops = ops + 1;
for (int i = 0; i < n; i = i + 1) ops = ops + 1;
std::cout << ops << '\n'; // n=3 olduqda 6 olacaq
}
Daxili dövr bir neçə xətti dövrdən «qalib gəlir»
#include <iostream>
int main() {
int n = 0;
std::cin >> n;
long long ops = 0;
for (int i = 0; i < n; i = i + 1) {
for (int j = 0; j < n; j = j + 1) ops = ops + 1;
}
std::cout << ops << '\n'; // n=100 olduqda 10000 olacaq
}
Hətta «iki əlavə xətti dövr» əlavə etsəniz belə, əsas töhfə N² olacaq, çünki N² çox daha sürətlə artır.
break xilas edərmi? Bəzən iş vaxtını qısaldır, amma struktur dəyişmir
İstəyirsiniz deyə bilərsiniz: «Yaxşı, mənim iki daxili dövrüm var, amma daxildə break edirəm, deməli hər şey yaxşıdır». Bəzən bu konkret icranı sürətləndirir. Amma Big‑O adətən işi «ümumilikdə» necə artdığı və ən pis hal üzrə danışır.
Əgər break erkən işləyirsə — yaxşıdır. Əgər işləmir və ya gec işə düşürsə — demək hələ də demək olar ki, tam kvadrat alacaqsınız. Buna görə faydalı vərdiş: break kömək edə bilər, amma «N dəfə N» strukturuna şübhə ilə yanaşmaq lazımdır, siz çıxışı dəqiq bildikdən sonra rahat ola bilərsiniz.
#include <iostream>
int main() {
int n = 0;
std::cin >> n;
bool found = false;
long long ops = 0;
for (int i = 0; i < n; i = i + 1) {
for (int j = 0; j < n; j = j + 1) {
ops = ops + 1;
if (i == n - 1 && j == n - 1) { // ən sonda "tapıldı"
found = true;
break;
}
}
if (found) break;
}
std::cout << ops << '\n'; // təxminən n*n
}
5. Praktik nümunə: təcrübələr üçün “LoopLab”
Mövzu fəlsəfə kimi qalmaması üçün kiçik bir «stend» yığacağıq — istifadəçiyə n daxil etməyə və müxtəlif konstruksiyaların: xətti, kvadratik və üçbucaq-oxşar olanların neçə «addım» etdiyini görməyə imkan verən proqram.
Biz real profilləşdirici etməyəcəyik: sadəcə iterasiyaları sayıb ədədləri çıxardacağıq. Təhsil tapşırıqlarında bu yanaşma alətlər olmadan ölçü hissi verir.
Sadə menyunu if/else ilə edək (hələ switch-i keçməmişik, ona görə istifadə etmirik).
“LoopLab” skeleti rejim seçimi ilə
#include <iostream>
int main() {
int mode = 0;
int n = 0;
std::cin >> mode >> n; // məs. "2 100"
if (mode == 1) {
int ops = 0;
for (int i = 0; i < n; i = i + 1) ops = ops + 1;
std::cout << ops << '\n';
} else if (mode == 2) {
long long ops = 0;
for (int i = 0; i < n; i = i + 1)
for (int j = 0; j < n; j = j + 1) ops = ops + 1;
std::cout << ops << '\n';
} else {
std::cout << "Unknown mode\n";
}
}
Artıq oynamaq olar: rejim 1 O(N)-i, rejim 2 isə O(N²)-i göstərir.
Rejim 3-ü «üçbucaq» olaraq əlavə edək
#include <iostream>
int main() {
int mode = 0, n = 0;
std::cin >> mode >> n;
if (mode == 3) {
long long ops = 0;
for (int i = 0; i < n; i = i + 1)
for (int j = 0; j < i; j = j + 1) ops = ops + 1;
std::cout << ops << '\n';
}
}
İndi, əgər siz 3 5 yazsanız, 10 görəcəksiniz; əgər 3 1000 yazsanız, 499500 görəcəksiniz — nəticə artıq böyükdür və təxminən «kvadrat» kimi artır.
Rejim 4: «kvadrat, amma bəzən erkən çıxırıq»
#include <iostream>
int main() {
int mode = 0, n = 0;
std::cin >> mode >> n;
if (mode == 4) {
long long ops = 0;
for (int i = 0; i < n; i = i + 1) {
for (int j = 0; j < n; j = j + 1) {
ops = ops + 1;
if (i == 0 && j == 0) break; // çox erkən çıxırıq
}
}
std::cout << ops << '\n'; // hər n üçün təxminən n olacaq (hər sətirdə 1 addım)
}
}
Burada maraqlı məqam: struktur daxililə baxanda daxili dövr olsa da, break nəticəsində xarici dövrün hər iterasiyasında yalnız bir daxili addım icra edilir. Nəticədə praktik olaraq xətti, yəni təxminən N alınır.
Bu yaxşı xatırlatmadır ki, O(…) böyüməni təsvir edən dildir, pis/yaxşı möhürü deyil.
6. Tipik səhvlər
Səhv №1: N-i “dəyər” ilə yox, “ölçü” ilə qarışdırmaq.
Çox tez-tez qarışıqlıq olur: tələbə dövrü n-ə qədər yazır, amma sonra n-i «öz ədədi» kimi düşünür, «ölçü» kimi yox. Məsələn, əgər n elementlərin sayıdırsa, N məhz «neçə element» deməkdir, hansı elementlər olduğuna deyil. Çətinlikdə bizim marağımız say üzrə böyümədir, yoxsa müqayisə uyğun olmayacaq.
Səhv №2: hər prosessor əməliyyatını saymağa çalışmaq və detallara batmaq.
Big‑O ilə ilk tanışlıqda asanlıqla özünüzlə mübahisə etməyə başlayırsınız: «Müqayisə də əməliyyatdır? i = i + 1 bir yox, iki əməliyyatdır?» Əgər belə edirsinizsə — normal insansınız, amma indi Big‑O başqa şeyi nəzərdə tutur: mikrodetailləri yox, əsas iş parçasının neçə dəfə təkrarlanmasını saymaq lazımdır.
Səhv №3: kod qısa olduğuna görə daxililiyi görməməzlikdən gəlmək.
İki dövr çox kompakt yazıla bilər, xüsusən mötərizəsiz olduqda. Buna görə vizual olaraq «cəmi iki sətir var» kimi görünə bilər. Praktikada bu milyon iterasiya daxilində milyon ola bilər. Təhsil kodunda məqsədli şəkildə {} qoymaq və indentasiyanı elə tutmaq yaxşıdır ki, göz dərhal görsün: «bu dövr dövrün içindədir».
Səhv №4: break-in avtomatik olaraq O(N²)-ni O(N)-ə çevirdiyinə inanmaq.
break həqiqətən icranı xeyli sürətləndirə bilər, amma bu, nə vaxt işlədiyinə bağlıdır. Əgər cavab adətən tez tapılırsa — orta halda kod demək olar ki, xətti davranış göstərə bilər. Amma əgər çox vaxt daxili dövr demək olar ki, tam işlənməlidirsə — yenə demək olar ki, kvadrat alacaqsınız. Ona görə break amnistiya deyil, anlamaq lazım olan bir alətdir.
Səhv №5: sərhədlərdə off-by-one və böyümə barədə yanlış nəticələr.
Əgər təsadüfən i <= n yazmısınızsa, i < n əvəzinə, yalnız bir iterasiya əlavə etmisiniz və sıra dəyişməyəcək. Amma kiçik N-lərdə qəribə rəqəmlər ala bilərsiniz və ideyadan şübhələnə bilərsiniz. Buna görə belə şeyləri yoxlayarkən çox kiçik N-lərdə (0, 1, 2, 3) nümunələri işlədib mənanın uyğun olub-olmadığını yoxlamaq faydalıdır.
GO TO FULL VERSION