Statik mürəkkəblik
Alqoritmlərin vaxt mürəkkəbliyinin təhlili, effektiv proqramların yaradılması üçün vacib bir vasitədir. Xətti vaxtda icra olunan alqoritmlər, eyni tapşırığı yerinə yetirmək üçün kvadratik vaxt tələb edən alqoritmlərdən xeyli sürətlidir. Buna görə də, xətti vaxtda işləyən alqoritmlərə üstünlük verilməlidir.
Adətən, alqoritmin icra vaxtı n - giriş məlumatlarının "ölçüsü" ilə müqayisədə müəyyən edilir. Bu ölçü, sıralanmalı olan obyektlərin sayı, çoxbucağın nöqtələrinin sayı və s. ola bilər. Alqoritmin vaxt mürəkkəbliyinin n ilə asılılıq düsturunu müəyyən etmək çətin bir vəzifə olduğundan, bunu avtomatlaşdırmaq mümkün olsaydı, əla olardı. Təəssüf ki, ümumi halda bu mümkün deyil. Lakin bu tapşırıqda biz bunu etmək mümkün olan çox sadə təbiətli proqramları nəzərdən keçirəcəyik. Nəzərdən keçirilən proqramlar aşağıdakı BNF qaydalarına uyğun olaraq yazılmışdır, burada <rəqəm> istənilən qeyri-mənfi tam ədəd ola bilər:
<Proqram>::="BEGIN"<Operatorlar siyahısı>"END"
<Operatorlar siyahısı>::=<Operator>|<Operator><Operatorlar siyahısı>
<Operator>::=<LOOP Operatoru>|<OP Operatoru>
<LOOP Operatoru>::=<LOOP Başlığı><Operatorlar siyahısı>"END"
<LOOP Başlığı>::="LOOP"<rəqəm>|"LOOP n"
<OP Operatoru>::="OP"<rəqəm>
Belə bir proqramın icra vaxtı aşağıdakı kimi hesablana bilər: OP operatorunun icrası, parametrində göstərilən qədər vaxt vahidi tələb edir. LOOP operatorunda yerləşdirilmiş operatorlar siyahısı, operatorun parametrində göstərilən qədər dəfə icra olunur, yəni ya verilmiş sabit sayda, əgər rəqəm verilmişdirsə, ya da parametr n olarsa n dəfə. Operatorlar siyahısının icra vaxtı, onun hissələrinin icra vaxtlarının cəminə bərabərdir. Beləliklə, proqramın icra vaxtı ümumilikdə n-dən asılıdır.
Giriş verilənləri
Birinci sətirdə k tam ədədi - giriş faylında proqramların sayı var. Sonra verilmiş qrammatikaya uyğun gələn k proqram gəlir. Boşluqlar və sətir keçidləri proqramda hər yerdə ola bilər, lakin BEGIN, END, LOOP və OP açar sözlərində, həmçinin tam ədədlərdə yoxdur.
LOOP operatorlarının iç-içəlik dərəcəsi 10-u keçmir, giriş faylının ölçüsü 2 KB-dan çox deyil, cavabda çoxhədlinin əmsalları 50000-i keçmir.
Çıxış verilənləri
Hər bir proqram üçün əvvəlcə proqramın nömrəsi ilə bir sətir gəlir. Növbəti sətirdə proqramın n terminlərində iş vaxtı yazılır - dərəcəsi 10-dan çox olmayan çoxhədli. Çoxhədli adi şəkildə yazılmalıdır, yəni oxşar toplananlar birləşdirilməlidir, daha yüksək dərəcəli toplananlar daha aşağı dərəcəli toplananlardan əvvəl gəlməlidir, əmsalı 0 olan toplananlar yazılmır, 1 çarpanları yazılmır. İkinci sətirin ümumi görünüşü "Runtime = a*n^10+b*n^9+...+i*n^2+j*n+k". Əgər icra vaxtı sıfırdırsa, "Runtime = 0" çıxarılmalıdır. Çoxhədli ilə sətirdən sonra boş bir sətir gəlməlidir, son test halı istisna olmaqla.