Zaman mürəkkəbliyi

Alqoritmlərin analizində geniş istifadə olunan funksiyaların qrafikləri; hər bir funksiya üçün giriş ölçüsü $n$-dən asılı olaraq əməliyyatların sayını $N$ göstərir.

Zaman mürəkkəbliyi — nəzəri informatikada alqoritmin icrası üçün tələb olunan kompüter vaxtının miqdarını təsvir edən hesablama mürəkkəbliyi. Zaman mürəkkəbliyi adətən alqoritm tərəfindən yerinə yetirilən elementar əməliyyatların sayı hesablanmaqla qiymətləndirilir və hər bir elementar əməliyyatın icrası üçün sabit vaxt tələb olunduğu fərz edilir. Buna görə də alqoritmin icrasına sərf olunan vaxt ilə onun yerinə yetirdiyi elementar əməliyyatların sayının sabit əmsalla bir-biri ilə əlaqəli olduğu qəbul edilir.

Alqoritmin icra müddəti eyni ölçülü müxtəlif girişlər üçün fərqli ola bildiyindən, adətən ən pis hal üzrə zaman mürəkkəbliyi nəzərə alınır. Bu, verilmiş ölçüdəki girişlər üçün tələb olunan maksimum icra vaxtını ifadə edir. Daha az istifadə olunan və adətən açıq şəkildə göstərilən orta hal üzrə mürəkkəblik isə verilmiş ölçüdəki girişlər üçün sərf olunan vaxtın orta qiymətidir (bu yanaşma məntiqlidir, çünki verilmiş ölçü üçün mümkün girişlərin sayı sonludur). Hər iki halda zaman mürəkkəbliyi, ümumiyyətlə, girişin ölçüsünün funksiyası kimi ifadə olunur. Bu funksiyanı dəqiq hesablamaq ümumiyyətlə çətin olduğundan və kiçik ölçülü girişlər üçün icra vaxtı adətən əhəmiyyət kəsb etmədiyindən, əsas diqqət giriş ölçüsü artdıqca mürəkkəbliyin davranışına, yəni onun asimptotik davranışına yönəldilir. Buna görə də zaman mürəkkəbliyi adətən böyük O notasiyası ilə ifadə olunur; tipik nümunələrə $O(n)$, $O(n\log n)$, $O(n^{\alpha })$, $O(2^{n})$ və s. daxildir. Burada $n$ girişi təsvir etmək üçün tələb olunan bitlərin sayı ilə ölçülən giriş ölçüsüdür.

Alqoritmik mürəkkəbliklər böyük O notasiyasında istifadə olunan funksiyanın növünə görə təsnif edilir. Məsələn, zaman mürəkkəbliyi $O(n)$ olan alqoritm xətti vaxt alqoritmi, zaman mürəkkəbliyi hər hansı $\alpha >0$ sabiti üçün <math>O(n^\alpha)</math olan alqoritm isə polinomial vaxt alqoritmidir.