termíny o (log log n) se mohou zobrazovat na různých místech, ale obvykle existují dvě hlavní trasy, které dorazí v tomto běhu.
zmenšení o druhou odmocninu
jak je uvedeno v odpovědi na propojenou otázku, běžným způsobem, jak algoritmus má časovou složitost O (log n), je, aby tento algoritmus pracoval opakovaným snížením velikosti vstupu o nějaký konstantní faktor při každé iteraci. Pokud tomu tak je, algoritmus musí ukončit po iteracích O (log n), protože po provedení dělení o(log n) konstantou musí algoritmus zmenšit velikost problému na 0 nebo 1. Proto má například binární vyhledávání složitost O (log n).
zajímavé je, že existuje podobný způsob zmenšení velikosti problému, který poskytuje Runtime formuláře O (log log n). Místo toho, abychom rozdělili vstup na polovinu v každé vrstvě, co se stane, když vezmeme druhou odmocninu velikosti V každé vrstvě?
Vezměme si například číslo 65 536. Kolikrát to musíme vydělit 2, dokud se nedostaneme na 1? Pokud to uděláme, dostaneme
- 65,536 / 2 = 32,768
- 32,768 / 2 = 16,384
- 16,384 / 2 = 8,192
- 8,192 / 2 = 4,096
- 4,096 / 2 = 2,048
- 2,048 / 2 = 1,024
- 1,024 / 2 = 512
- 512 / 2 = 256
- 256 / 2 = 128
- 128 / 2 = 64
- 64 / 2 = 32
- 32 / 2 = 16
- 16 / 2 = 8
- 8 / 2 = 4
- 4 / 2 = 2
- 2 / 2 = 1
tento proces trvá 16 kroků, a to je také případ, že 65,536 = 216.
ale pokud vezmeme druhou odmocninu na každé úrovni, dostaneme
- √65,536 = 256
- √256 = 16
- √16 = 4
- √4 = 2
Všimněte si, že to trvá jen čtyři kroky se dostat celou cestu dolů 2. Proč je tohle?
nejprve intuitivní vysvětlení. Kolik číslic je v číslech n A √n? V čísle n je přibližně log n číslic a přibližně log (√n) = log (n1 / 2) = (1/2)log n číslic v √n. To znamená, že pokaždé, když vezmete druhou odmocninu, zhruba snížíte počet číslic v čísle na polovinu. Protože můžete snížit pouze na polovinu množství k O (log K) krát, než klesne na konstantu (řekněme, 2), to znamená, že můžete vzít pouze odmocniny O (log log n) krát, než snížíte číslo na nějakou konstantu (řekněme, 2).
Nyní, pojďme udělat nějakou matematiku, aby to přísné. Le ‚ TS přepíše výše uvedenou sekvenci z hlediska pravomocí dvou:
- √65,536 = √216 = (216)1/2 = 28 = 256
- √256 = √28 = (28)1/2 = 24 = 16
- √16 = √24 = (24)1/2 = 22 = 4
- √4 = √22 = (22)1/2 = 21 = 2
Všimněte si, že jsme postupovali podle sekvence 216 → 28 → 24 → 22 → 21. Při každé iteraci jsme snížili exponent síly dvou na polovinu. To je zajímavé, protože se to spojuje s tím, co již víme – číslo k můžete rozdělit pouze na polovinu o (log k) krát, než klesne na nulu.
takže vezměte libovolné číslo n a napište jej jako n = 2k. Pokaždé, když vezmete druhou odmocninu z n, snížíte exponent v této rovnici na polovinu. Proto mohou být použity pouze o (log k) odmocniny, než k klesne na 1 nebo nižší (v tomto případě N klesne na 2 nebo nižší). Protože n = 2k to znamená, že k = log2 n, a proto počet odmocnin je o (log k) = O (log log n). Pokud tedy existuje algoritmus, který funguje tak, že opakovaně redukuje problém na podproblém velikosti, který je druhou odmocninou původní velikosti problému, tento algoritmus skončí po krocích O (log log n).
jedním z příkladů v reálném světě je datová struktura stromu van Emde Boas (veb-tree). Veb-strom je specializovaná datová struktura pro ukládání celých čísel v rozsahu 0 … N-1. Funguje to následovně: kořenový uzel stromu má v sobě √N ukazatele, rozdělující rozsah 0 … N-1 do √N kbelíků, z nichž každá drží rozsah zhruba √n celých čísel. Tyto kbelíky jsou pak každá vnitřně rozdělena na √ (√n) kbelíky, z nichž každá drží zhruba √(√ N) prvky. Chcete-li procházet stromem, začnete u kořene, určete, do kterého kbelíku patříte, a poté rekurzivně pokračujte v příslušném podstromu. Vzhledem k tomu, jak je veb strom strukturován, můžete v O(1) čase určit, do kterého podstromu sestoupit, a tak po krocích O (log log N) dosáhnete dna stromu. Proto vyhledávání ve stromu veb trvá pouze O (log log N).
dalším příkladem je algoritmus nejbližší dvojice bodů Hopcroft-Fortune. Tento algoritmus se pokouší najít dva nejbližší body ve sbírce 2D bodů. Funguje to tak, že vytvoří mřížku kbelíků a rozdělí body do těchto kbelíků. Pokud je v kterémkoli bodě algoritmu nalezen kbelík, který má více než √N bodů, algoritmus rekurzivně zpracovává tento kbelík. Maximální hloubka rekurze je tedy O (log log n) a pomocí analýzy rekurzního stromu lze ukázat, že každá vrstva ve stromu funguje O(n). Proto je celková doba běhu algoritmu O (n log log n).
o (log n) algoritmy na malých vstupech
existují některé další algoritmy, které dosahují doby běhu O (log log n) pomocí algoritmů, jako je binární vyhledávání na objektech velikosti O (log n). Například datová struktura x-fast trie provádí binární vyhledávání nad vrstvami at stromu výšky O (log U), takže runtime pro některé z jeho operací je O (log log U). Související y-fast trie získává některé ze svých o (log log U) Runtime udržováním vyvážených BST uzlů o (log U), což umožňuje vyhledávání v těchto stromech běžet v čase O (log log U). Strom tango a související datové struktury stromu multisplay končí ve svých analýzách termínem O (log log n), protože udržují stromy, které obsahují položky O(log n).
další příklady
jiné algoritmy dosahují runtime o (log log n) jinými způsoby. Interpolační vyhledávání očekává, že runtime o (log log n) najde číslo v tříděném poli, ale analýza je poměrně zapojena. Analýza nakonec funguje tak, že ukazuje, že počet iterací se rovná číslu k tak, že n2-K ≤ 2, pro které je log log n správným řešením. Některé algoritmy, jako je Cheriton-Tarjan MST algoritmus, dorazí na runtime zahrnující O (log log n) řešením komplexního problému optimalizace s omezenými podmínkami.
doufám, že to pomůže!