Waqıt sarpı. Struktura ústinde ámel orınlaw algoritmin atqarılıw waqtın esaplaw
názerde tutıladı. Bunı esaplawda ataqlı úlken “O” notaciya túsinikti isletedi.
Yad sarpı. Kiriw maǵlıwmatların esapqa almaǵan halda, qollanılıp atırǵan
algoritm ushın yadtan talap etiletuǵın qosımsha orın ajıratılıwı túsiniledi. Bunda da
úlken “O” notaciyası qollanıladı.
Waqıt hám yad sarpın esaplaw ushın tómendegi jandasıwlar bar:
- U’lken O notaciya. f(x)=O(g(n)) dep belgilenedi, tek hám tek sonday oń c
hám m konstanta bar bolıp, f(n)<=c*g(n) teńsizlik orınlı bolsa, barlıq n, n>=m
ja
ǵdaylarda. Mısalı, bul funkciyanı 3n+2=O(n) dep alıw múmkin, sebebi
3n+2<=4n, n>=2 teńsizlik orınlı. Bul funktsiyanı 6*2
n
+n
2
=O(2
n
) dep alıw múmkin,
sebebi n>=4 ushın 6*2
n
+n
2
<=7*2
n
ańlatpa orınlı. O(1) dep esaplaw waqtı
ózgermes bol
ǵan jaǵdaydı belgileymiz. O(n
2
) ni kvadratlıq, O(n
3
) ti kublıq, O(2
n
)
ni eksponencial dep ataladı. Eger algoritm orınlanıw waqtı O(log n) bolsa, O(n)
ǵa
qara
ǵanda tez algoritm dep esaplanadı.
- Omega notaciya.f(x)=Ω(g(n)) dep belgilenedi, tek hám tek sonday oń c
hám m konstanta bar bolıp, f(n)<=c*g(n) teńsizlik orınlı bolsa, barlıq n, n>=m
ja
ǵdaylarda. Mısalı, bul funkciyanı 3n+2=Ω(n) dep alıw múmkin, sebebi
3n+2>=3n, n>=1 teńsizlik orınlı. Bul funktsiyanı 6*2
n
+n
2
=Ω(2
n
) dep alıw múmkin,
sebebi n>=1 ushın 6*2
n
+n
2
>=6*2
n
ańlatpa orınlı.
- Teta notaciya. (x)=θ(g(n)) dep belgilenedi, tek hám tek sonday oń c hám
m konstanta bar bolıp, f(n)<=c*g(n) teńsizlik orınlı bolsa, barlıq n, n>=m
ja
ǵdaylarda. Mısalı, bul funkciyanı 3n+2=θ(n) dep belgilew múmkin, sebebi
3n+2>=3n, n>=1 hám 3n+2<=4n barlıq n>=2 de teńsizlik orınlı. Bul funktsiyanı
6*2
n
+n
2
=θ(2
n
) dep alıw múmkin.
