Шта је колико брзо¶
Видели смо да за неке програме број операција које се изврше (а тиме и време рада програма) расте пропорционално величини улаза. То су програми са алгоритмима линеарне сложености, и за њихово време извршавања пишемо \(t(n)=O(n)\). Ово се чита „време рада алгоритма \(t(n)\) припада класи О од ен”, или краће, неформално: „време рада алгоритма \(t(n)\) је О од ен”. Често кажемо и: „алгоритам је сложености О од ен”.
Такозвана „Велико О” нотација (википедија) је прецизно дефинисана и интензивно се користи у рачунарској науци. Овде ћемо је користити само за именовање одређених класа сложености алгоритама и најједноставније рачунање (у следећем поглављу).
Слично томе, за време рада алгоритма квадратне сложености пишемо \(t(n)=O(n^2)\) („О од ен на квадрат”).
Постоје и алгоритми чије време извршавања је приближно сразмерно другим математичким функцијама од \(n\) и тада говоримо о другачијим сложеностима алгоритма. Следи мала табела неких сложености које се често појављују (наведене су редом по брзини раста при повећавању n), а детаљнију табелу можете наћи овде:
| Сложеност | Ознака | Пример |
|---|---|---|
| Константна | \(O(1)\) | Налажење максимума у сортираном низу |
| Логаритамска | \(O(Lg(n))\) | Бинарна претрага |
| Корен од n | \(O(\sqrt{n})\) | Испитивање да ли је природан број прост, факторизација прородног броја |
| Линеарна | \(O(n)\) | Један пролаз кроз низ дужине \(n\) (на пр. учитавање низа, сабирање елемената низа) |
| Ен-лог-ен (квазилинеарна) | \(O(n Lg(n))\) | Сортирање низа (најбржи могући алгоритми за општи случај) |
| Квадратна | \(O(n^2)\) | Учитавање матрице величине \(n \times n\) |
| Кубна | \(O(n^3)\) | Множење две квадратне матрице (наиван алгоритам) |
| Експоненцијална | \(O(2^n)\) | Налажење свих подскупова супа од \(n\) елемената |
| Факторијелна | \(O(n!)\) | Налажење свих пермутација бројева од 1 до \(n\) |
Функција \(Lg(n)\) која се појављује у табели, дефинисана је са \(Lg(n) = \lceil Log_2(n)\rceil\), односно као логаритам основе 2, заокружен навише.
За читаоце којима појам логаритма (још) није познат из математике, функцију \(Lg(n)\) за природан број \(n\) можемо равноправно да дефинишемо као цео број којим треба степеновати број 2 да се добије \(n\), или да се добије најближи степен двојке који није мањи од \(n\).
Исто то, записано формулом: \(Lg(n) = min\{k \in N : n \leq 2^k\}\).
Још један начин да задамо функцију \(Lg(n)\) на скупу природних бројева је: ако је \(k \in N~\) и \(~2^{k-1} < n \leq 2^k\), онда је \(Lg(n) = k\)
Непосредно из дефиниције следи да за сваки природан број \(k\) важи \(Lg(2^k) = k\). На пример: \(~Lg(2) = 1\), \(~Lg(4) = 2\), \(~Lg(8) = 3\), \(~Lg(16) = 4\), \(~Lg(1024) = 10\), итд.
Такође важи \(Lg(2n) = Lg(n) + 1~\) и као последица \(Lg(2^k \cdot n) = Lg(n) + k~\). На пример \(~Lg(1600) = Lg(100) + 4 = 7 + 4 = 11\)
У пракси, за груба израчунавања напамет, врло је корисна приближна једнакост \(10^3 = 1000 \approx 1024 = 2^{10}\), јер из ње следи \(10^{3n} \approx 2^{10 n}\) и \(~Lg(10^{3n}) \approx 10n\). У ствари, у последњој приближној једнакости се знак \(\approx\) може заменити једнакошћу за свако природно \(n < 30\), тако да важи чак и \(Lg(10^{87}) = 290\), а не само \(Lg(10^{87}) \approx 290\). Са овако великим бројевима врло ретко имамо посла, па можемо сматрати да за практичне потребе важи једнакост. Тако имамо \(Lg(1~000) = 10\), \(~Lg(1~000~000) = 20\), \(~Lg(1~000~000~000) = 30\), \(~Lg(2~000~000~000) = 31\), \(~Lg(4~000~000~000) = 32\), \(~Lg(1~000~000~000~000~000~000) = 60\), \(~Lg(16~000~000~000~000~000~000) = 64\), …
Од интереса је да се стекне нека представа о томе за колико велике улазне податке неки алгоритам може да се изврши у одређеном времену. То наравно зависи од брзине извршавања појединачних операција, што опет зависи од конкретног рачунара, програмског језика (односно компајлера или интерпретера), од једноставности тих појединачних операција итд. Пошто је у овако опште постављеном питању превелики број фактора који утичу на одговор, можемо добити само грубу оријентацију.
Шта могу за ово време¶
Усвојимо процену да савремени рачунар (зависно од поменутих фактора) може да изврши 10 до 100 милиона операција у секунди. Ова процена је вероватно сувише опрезна, у смислу да је могуће усвојити и претпоставку да је тај број операција већи, нарочито у оптималним условима (што са Пајтоном у старту није случај, јер се интерпретира). Ипак, боље је да се применом ових процена обрадујете (то јест, да вам програм буде нешто бржи него што сте предвидели) него да се разочарате.
Уз усвојену претпоставку можемо израчунати за колико велике улазне податке се може извршити број операција наведен у табели (као функција од \(n\)) у разним интервалима времена.
| Број операција | за секунду | за минут | за сат | за дан | за годину | за век |
|---|---|---|---|---|---|---|
| \(Lg(n)\) | \(\infty\) | \(\infty\) | \(\infty\) | \(\infty\) | \(\infty\) | \(\infty\) |
| \(\sqrt{n}\) | \(10^{14}\) - \(10^{16}\) | \(3 \cdot 10^{17}\) - \(3 \cdot 10^{19}\) | \(10^{21}\) - \(10^{23}\) | \(8 \cdot 10^{23}\) - \(8 \cdot 10^{25}\) | \(10^{29}\) - \(10^{31}\) | \(10^{33}\) - \(10^{35}\) |
| \(n\) | 10-100 м. | 0.6 - 6 млрд. | 36 - 360 млрд. | \(9 \cdot 10^{11}\) - \(9 \cdot 10^{12}\) | \(3 \cdot 10^{14}\) - \(3 \cdot 10^{15}\) | \(3 \cdot 10^{16}\) - \(3 \cdot 10^{17}\) |
| \(n \cdot Lg(n)\) | 0.5 - 4.5 м. | 24 - 216 м. | 1 - 10 млрд. | 25 - 228 млрд. | \(7.2 \cdot 10^{12}\) - \(6.7 \cdot 10^{13}\) | \(6 \cdot 10^{14}\) - \(6 \cdot 10^{15}\) |
| \(n^2\) | 3 - 10 х. | 24 -77 х. | 200 - 600 х. | 0.9 - 3 м. | 17 - 55 м. | 170 - 560 м. |
| \(n^3\) | 200 - 450 | 800 - 1800 | 3 - 7 х. | 10 - 20 х. | 65 -150 х. | 300 - 700 х. |
| \(2^n\) | 23 - 27 | 29 - 32 | 35 - 38 | 40 -43 | 48 - 51 | 55 - 58 |
Објашњења уз табелу:
- Симбол \(\infty\) у табели изнад означава да (што се алгоритма тиче) улаз који би стигао да се обради може да буде толико велики, да ће реално бити ограничен другим факторима (на пример меморијом рачунара), а не брзином алгоритма.
- Ознака х. стоји за хиљаде, м. за милионе а млрд. за милијарде
- Вредности су додатно заокруживане, јер су ионако приближне и служе само за оријентацију.
Колико времена ми треба за ово¶
Слично претходној табели, можемо да формирамо и обрнуту табелу, која показује колико је времена потребно алгоритмима различите сложености да обраде улазе датих величина:
| Број операција | n = 10 | n = 100 | n = 1000 | n = 10 000 | n = 100 000 | n = 1 000 000 | n = 10 000 000 |
|---|---|---|---|---|---|---|---|
| \(Lg(n)\) | < 1 \(\mu s\) | < 1 \(\mu s\) | < 1 \(\mu s\) | < 1 \(\mu s\) | < 1 \(\mu s\) | \(\approx 1 \mu s\) | \(\approx 1 \mu s\) |
| \(\sqrt{n}\) | 0.03 - 0.3 \(\mu s\) | 0.1 - 1 \(\mu s\) | 0.3 - 3 \(\mu s\) | 1 - 10 \(\mu s\) | 3 - 30 \(\mu s\) | 1 - 10 \(\mu s\) | 0.03 - 0.3 ms |
| \(n\) | 0.1 - 1 \(\mu s\) | 1 - 10 \(\mu s\) | 0.01 - 0.1 ms | 0.1 - 1 ms | 1 - 10 ms | 10 - 100 ms | 0.1 - 1 s |
| \(n \cdot Lg(n)\) | 0.3 - 3 \(\mu s\) | 6 - 60 \(\mu s\) | 0.1 - 1 ms | 1 - 13 ms | 10 - 170 ms | 0.2 - 2 s | 2.3 - 23 s |
| \(n^2\) | 1 - 10 \(\mu s\) | 0.1 - 1 ms | 10 - 100 ms | 1 - 10 s | 2 - 20 min | 3 - 28 h | 12 - 116 d |
| \(n^3\) | 0.01 - 0.1 ms | 10 - 100 ms | 10 - 100 s | 3 - 28 h | 0.3 - 3 g | 0.3 - 3 mil | 300 - 3000 mil |
| \(2^n\) | 0.01 - 0.1 ms | \(10^{16}\) g | \(10^{284}\) g |
Ознаке у табели: \(\mu s\) - микросекунда, ms - милисекунда, s - секунда, min - минут, h - сат, d - дан, g - година, mil - миленијум (хиљаду година)
Поља у последњем реду нису попуњена јер немају никакву употребну вредност, а практично је немогуће и схватити о колико огромним временима се ради. Да би било нешто јасније о каквим бројевима је реч, направићемо малу рачуницу. Из табеле читамо да је алгоритму за налажење свих подскупова скупа од 100 елемената (то је \(2^n\) операција, уз претпоставку да извршава само једну операцију по подскупу) потребно реда \(10^{16}\) година. Колико је то стварно? Процењује се да је старост васионе реда \(10^{10}\) година, што значи да би се поменути алгоритам за скуп од 100 елемената извршио отприлике за време за које би се комплетна васиона до данашњег стања формирала милион пута. За 110 елемената би требало милијарду старости васионе, а за 200 елемената потребно време умемо само формално да изразимо, а реално немамо ни име ни било какво поређење за тај број.
Са друге стране, за алгоритам логаритамске сложености практично нема ограничења величине улазних података, бар што се тиче самог алгоритма. На пример и за милијарду милијарди података је алгоритму логаритамске сложености потребно свега неколико десетина операција, јер је \(Lg(10^{18}) = Lg(2^{60}) = 60\), а за тих неколико десетина операција са 10 милиона операција у секунди, потребно време је и даље у микросекундама. При томе говоримо о тешко појмљивој количини меморије. Поново ћемо се мало заиграти рачуном да бисмо дочарали колико је та меморија далеко од свакодневне праксе. Чак и кад би један податак стао у један бит (најмања могућа количина меморије), укупна меморија потребна за толико података је реда \(10^{18} b \approx 10^{17} B \approx 10^8 GB\), дакле сто милиона гигабајта. Када бисмо истовремено читали по \(100 GB\) у минуту са хиљаду дискова (величине 100 терабајта, ако такви постоје), и даље би било потребно око 1000 минута само за копирање толико података (а питање је и где бисмо толике податке копирали).
Сваки алгоритам у принципу може да се анализира ради процене његове сложености, односно одређивања реда величине броја операција које се изврше током рада алгоритма. Ми смо то већ урадили за два једноставна програма који рачунају суме (један линеарне и један квадратне сложености), а постоје поступци за анализу и много сложенијих алгоритама.
Када знамо класу сложености којој неки алгоритам припада, на основу горе наведених табела најчешће можемо да стекнемо представу о томе да ли је тај алгоритам довољно брз да у одређеном времену обради податке одређене величине.
На пример, ако је потребно решити неки задатак за улазне податке величине \(n=100~000\), видимо да:
- за алгоритам квадратне сложености треба очекивати да се потребно време изражава у десетинама минута (при повољним условима можда и у минутима)
- за алгоритам од \(n \cdot Lg(n)\) операција, очекивано време је реда десетинке секунде
- за алгоритам од \(n\) операција, време треба да је мање од стотинке секунде
Према томе, ако за извршавање над улазним подацима величине \(100~000\) имамо на располагању пет секунди, не треба рачунати на квадратни алгоритам, док би линеарни алгоритам, или алгоритам сложености \(O(n Lg(n))\) извесно обавили посао на време.
Слично томе, за улазне податке величине \(1~000~000~000\) и време до две десетинке секунде:
- алгоритам линеарне сложености би захтевао време у десетинама секунди, па није довољно брз
- за алгоритам са \(\sqrt{n}\) операција, можемо очекивати време од неколико милисекунди, што је у складу са захтевима
- за алгоритам сложености \(O(Lg(n))\), очекивано време је у микросекундама, што је одлично
- за алгоритам сложености \(O(1)\), коме је увек довољан константан број операција, очекивано време је још мање
Још неке напомене које треба имати на уму:
- За прецизније процене треба узети у обзир и константу која стоји уз главни део израза у функцији која изражава број потребних операција. На пример, алгоритам коме треба \(10n^2\) операција је 10 пута спорији од алгоритма коме треба \(n^2\) операција.
- Овај начин процењивања је намењен за велике улазе и утолико је поузданији и смисленији што су величине улаза (а тиме и времена) већи. Времена у микросекундама и милисекундама у табели горе дата су само ради стицања представе о реду величине. Процене за мала времена не могу бити прецизне ако се раде на овај начин.
- Ово су све само општа правила, више осећаја се стиче обраћањем пажње на ове ствари у практичном раду.