Асимптотска сложеност (рачунарство)

У Теорија сложености асимптотска сложеност у рачунарству је употреба асимптотске анализе за процену сложености алгоритама и рачунарских проблема, обично у вези са нотацијом "Велико О". У смислу најчешће процењиваних рачунарских ресурса, најчешћа је временска сложеност и просторна сложеност.

Термин сложеност (алгоритама) се углавном односи на асимптотску сложеност.

Даље, уколико није другачије наглашено, термин "рачунарска сложеност" се обично односи на горњу границу асимптотске сложености алгоритма или проблема, која се обично пише у Велико-О нотацији; нпр. $O(n^{3}).$ Друге врсте процене асимптотске сложености су нотација доње границе (велико О | велико Омега ); нпр. Ω(н)) и асимптотски уске процене, када се горње и доње границе асимптоте поклапају (користи се "велико тета"); нпр. Θ(н лог н)).

Даља претпоставка је да сложеност у питању је сложеност најгорег слуцаја осим ако се другачије не нагласи. Алтернативни приступ је пробабилистичка анализа алгоритама.

У већни практичних случајева, ради се о детерминистичким алгоритама, иако теоријска информатика разматра недетерминистичке алгоритме и друге напредне моделе у рачунарству.

Види још

• Теорија комплексности
• Мастер теорема