ასიმპტოტური აღნიშვნა O-დიდი

ნოტაცია	სახელი
$O(1)$	მუდმივი
$O(\log \log n)$	ლოგ-ლოგარითმული
$O(\log n)$	ლოგარითმული
$O(n)$	წრფივი
$O(n\log n)=O(\log n!)$	ლოგწრფივი
$O(n^{2})$	კვადრატული
$O(c^{n})$ $\scriptstyle c>1$	ექსპონენციალური
$O(n!)$	ფაქტორიალური

O-დიდი – ასიმპტოტური აღნიშვნა, რომლის საშუალებით აღიწერება მოცემული ფუნქციის ყოფაქცევა ზღვარში, როცა არგუმენტი მიისწრაფება უსასრულობისკენ. ეს აღნიშვნები შემოღებულ იქნა, რათა რაც შეიძლება მოხერხებული კლასიფიკაცია შემოეღოთ ფუნქციებისთვის მათი ზრდის რიგის მიხედვით.

კომპიუტერულ მეცნიერებაში, O-დიდის აღნიშვნით აღწერენ, თუ როგორ იზრდება ალგორითმში დროის სირთულე და მეხსიერების მოთხოვნილება შემოტანილი მნიშვნელობის გაზრდისას. ძირითადად ის გამოიყენება ალგორითმის მუშაობის დროის შესაფასებლად უარეს შემთხვევაში. ამიტომ ეს შეფასება გვაძლევს ალგორითმის მუშაობის დროის ზედა ზღვარს ნებისმიერი შემავალი მონაცემისთვის.

ლიტერატურა

• ალგორითმები და მონაცემთა სტრუქტურები, კობა გელაშვილი.