"28n3" - 1 õppematerjal

Programmeerimiskeel

arvuti –mõnikord ei aita isegi parim algoritm •Keerulised algoritmid kasutavad vahetulemuste hoidmiseks ja nendega opereerimiseks andmestruktuure •Keerukuse analüüs annab aimu algoritmi headusest ja parema algoritmi olemasolust ITK 2007, Kalev Pihl Sissejuhatus informaatikasse 16 O notatsioon •O-notatsiooni abil määratakse funktsioonide keerukuse klassid. •Abstraheeritakse konstantsed kordajad ja väiksema keerukusega liidetavad O( 1000 n3log n+28n3+ 34 n+ 1000000 ) = O(n3log n) •Spetsiaalsed keerukusklassid: .logaritmiline:O(log n) .lineaarne:O(n) .ruutkeerukus:O(n2) .polünomiaalne:O(nk), k . 1 .eksponentsiaalne:O(an), n > 1 ITK 2007, Kalev Pihl Sissejuhatus informaatikasse 17 C:My DocumentsalgoritmidImage1_3.jpg ITK 2007, Kalev Pihl Sissejuhatus informaatikasse 18 Mis on suur ja mis on väike? .Minimaalsedsuurused: .Elektroniraadiusca 2.82 x 10-15m .Minimaalsedajad: .Aeg, misvõtabvalguselelektroniraadiuseläbimine: