Složitost O(n)

Pokud softwarový designer navrhuje celý aplikační systém a vytváří vlastnosti tohoto systému jen z případu užití - Use cases, očekává od systému něco co navrhl. Dle mého názoru by si ale měl i designér, který není programátorem měl uvědomit, že jeho návrhy mohou významně ovlivnit většinu algoritmů v systému. Výsledkem čehož je pomalejší provádění všech algoritmů a větší čas potřebný ke zpracování. Vezměme si například geniální myšlenku využívání dynamických datových struktur namísto statických. A k tomu si přidejme navíc využívání multihodnot namísto jednohodnotových položek.

Poznámka:
Příkladem multihodnoty z běžného života je telefon. Mohu mít více telefonních čísel, proto se hodnota telefon v dynamické struktuře vyskytuje vícekrát.

Podívejme se na to, jak se změní v celém systému složitosti algorimu po zavedení dynamických datových struktur. Pro zjednodušení neuvažujeme že hodnotou u dynamické datové struktury může být jakýkoliv datový typ, vliv variantního typu a nutnosti přetypování je zanedbán.

A . Máme statickou datovou strukturu
LibraryElement
• elementID
• Artist[50]
• Title[50]

B. Máme dynamickou datovou strukturu
LibraryElement – je pole
Item[1] – elementID
Item[2] – Artist
Item[3] – Artist
.
.
.
Item[10] – Title
Zpracování jedno údaje ve struktuře má složitost O(1).
Zpracování jedné informace
Příklad 1. Abych zobrazil jednu položku např. Artist potřebuji složitost
M – počet atributů nebo chceteli počet položek ve struktůře
A. O(1)
B. O(2) – obecně O(M)

Zpracování pole informací – zpracování celé knihovny
Příklad 2. Zobrazení knihovny o N prvcích
A – počet zobrazovaných atributů
A. O(N*A)
B. O(N*A*M)
Příklad 3.Třídění informací – quicksort O(N log2 N)
A. O(N log2 N)
B. O((N*M) log2 (N *M))
Příklad 4. Přenos informací – složitost potřebná k serializaci a deserializaci

A. O(N) – u statické struktůry tedy mohu mluvit jednoduše o přenosu X KB/s
Vím, že chci úřenést (2b + 50+50) * N
B. O(N*M) - u statické struktury není správné mluvit o X KB/s … protože proces serializace a deserializace má mnohem větší složitost