Asymptotická složitost: Porovnání verzí
Smazaný obsah Přidaný obsah
mBez shrnutí editace |
→Příklad výpočetní složitosti: Rozšířil jsem tabulku pro výpočetní náročnosti... |
||
Řádek 120:
Jako jednoduchý příklad můžeme uvést specifickou implementaci [[dynamické pole|dynamického pole]], která zdvojnásobuje velikost pole pokaždé, když dojde k jeho naplnění. V tomto případě je tedy nutná realokace, v nejhorším případě tato operace potřebuje čas až O(''N''). Samotné vkládání prvků (bez nutnosti realokace) vyžaduje čas O(1), pro ''N'' prvků tedy také O(''N''). Pro vložení ''N'' prvků (včetně realokace) je tedy potřeba O(''N'') + O(''N'') = O(''N''), amortizovaný čas na jedno vložení prvku je pak O(''N'')/''N'' = O(1).
== Příklad výpočetní
Jedna operace zde trvá jednu [[Nanosekunda|nanosekundu]].
{| class="wikitable" style="text-align:left"
! style="background:#ffdead;" rowspan="2" |
! colspan="
|-
!
|-
! <math>\log{\log{n}}</math>
|
|-
! <math>\log{n}</math>
|
|-
! <math>\sqrt{n}</math>
|
|-
! <math>n</math>
|
|-
! <math>n\log{n}</math>
|
|-
! <math>n^2</math>
| 100 ns || 400 ns || 3 μs || 10 μs || 1 ms || 16 min 40 s || 32 let ||
|-
! <math>n^3</math>
| 1 μs || 8 μs || 125 μs || 1 ms || 1 s || 32 let || ||
|-
! <math>n^4</math>
| 10 μs || 160 μs || 6 ms || 100 ms || 16 min 40 s || || ||
|-
! <math>2^n</math>
| 1 μs || 1 ms || 13 dní || || || || ||
|-
! <math>3^n</math>
| 59 μs || 4 s || 22 760 000 let || || || || ||
|-
! <math>n!</math>
| 4 ms || 77 let || || || || || ||
|-
! <math>n^n</math>
| 10 s || || || || || || ||
|}
| |||