Složenost algoritma

#fax #cs/prog [deo računarstva]

Efikasnost algoritma:

  • vremenska složenost
  • memorijska (prostorna) složenost
  • za neku konkretnu ulaznu veličinu
  • asimptotsko ponašanje kado veličina ulaza raste

Merenje i procenjivanje resursa

— Merenje vremena (na primer, u C-u pomoću biblioteke <time.h>).

— Procenjivanje vremena, ako znamo prosečno vreme za izvršavanje operacija.

— Profajliranje

  • analiza performansa programa;
  • koliko puta je bila pozvana i koliko vremena je utrošila funkcija.

Sa ovim znanjem možemo da razumemo koje (najčešće korišćene i koje najviše troše) funkcije treba da optimizujemo

Asimptotsko ponašanje

  • vreme izvršavanja — funkcija od broja argumenata
  • analiza najgoreg slučaja

— broj instrukcija za argumenata.

,

Def.

— klasa funkcija koje raste sporije od

Def.

— klasa funkcija koje raste brže od

Def.

— klasa funkcija koje raste slično kao i

Teorema. važi za , i :

  2. Tada:

Teorema.


  2. Odakle:

Primeri:

Def. — vreme izvršavanja algoritma za ulaz veličine , . Tada je algoritam složenosti (reda) .

Složenost algoritama obično se izražava u terminima , pri tome što se traži funkcija koja raste što sporije.

Na primer, .
Iako važi i i i ,
Kažemo da je taj algoritam složenosti .

Procenjivane u terminima je preciznije ali nije uvek moguće.

Na primer:
Za neke ulaze , a za neke , tada algoritam nije ni složenosti ni , ali jeste složenosti

Složenost:
— konstantna
— logaritamska
— linearna
— kvazilinearna
— kvadratna
— kubna
— polinomna
— eksponencijalna

Izračunavanje složenosti:

  • Vremenska:
    • Naredbe bez petlji i poziva funkcija —
    • Blok složenosti a posle blok —
    • if (...) else —
    • petlja sa iteracija i u telu —
    • petlja sa iteracija unutra petlji sa iteracija —
  • Prostorna:
    • bez poziva fja i dinamička alokacija —
    • alokacija elemenata složenosti —
    • alokacija niza od elemenata —
    • poziva fje složenosti iz fje složenosti —

Klasa .
Def. Algoritam sa ulaza je polinomske složenosti ako za neko .
Klasa problema za koje postoji algoritam sa označava se sa .

Problem zadovoljivosti:
Da li je zadovoljiva data logička formula od primenljivih?
kombinacija .
Pripada li problem klasi ? Nema dokaza ni da pripada ni da ne pripada.

Popravljanje složenosti

Vremenske:

  • Naći delove (funkcije) koje dominantno utiču na složenost
  • Prvo naći algoritam sa najboljim asimptotskim ponašanjem
  • Kada je asimptotsko ponašanje najbolje, smanjiti broj naredbi
  • Koristiti optimizaciju kompilatora
  • Izdvojiti ponavljajući izvršavanja (izdvojiti što više moguće izvan petlji)
  • [Prioritet vreme]: Čuvati neka ponavljajuća izračunavanja

Prostorne:

  • Najmanji mogući tipovi
  • [Prioritet memorija]: Ne čuvati stvari koje se lako računaju.