Amarengo

Articles and news

co by způsobilo, že algoritmus má složitost O(log log n)?

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!

Napsat komentář

Vaše e-mailová adresa nebude zveřejněna.