«amaliy matematika va informatika» kafedrasi «Algoritmlar nazariyasi» fanidan Mustaqil ish

Lineer vaqt

Chiziqli vaqt, yoki O ( n) agar uning murakkabligi O ( n). Norasmiy ravishda bu shuni anglatadiki, kirish hajmi etarlicha katta boʻlsa, ish vaqti kirish hajmi bilan chiziqli ravishda oshadi. Masalan, roʻyxatning barcha elementlarini yigʻadigan protsedura roʻyxat uzunligiga mutanosib vaqt talab etadi. Ushbu tavsif toʻliq aniq emas, chunki ish vaqti aniq mutanosiblikdan sezilarli darajada farq qilishi mumkin, ayniqsa kichik qiymatlar uchun. n.

Lineer vaqt koʻpincha algoritmning kerakli atributi sifatida qaraladi. Algoritmlarni (deyarli) chiziqli ish vaqti yoki undan yaxshiroq yaratish uchun juda koʻp tadqiqotlar oʻtkazildi. Ushbu tadqiqotlar dasturiy taʻminot va apparat yondashuvlarini oʻz ichiga olgan. Uskuna bajarilishida, baʻzi bir algoritmlar, matematik jihatdan, hech qachon standart hisoblash modellarida hech qachon chiziqli bajarilish vaqtiga erisha olmaydi, chiziqli vaqt ichida ishlashi mumkin. Ushbu maqsadga erishish uchun bir xillikdan foydalanadigan baʻzi bir apparat texnologiyalari mavjud. Masalan, assotsiativ xotira. Ushbu chiziqli vaqt tushunchasi Boyer-Mur va Ukkonen kabi qatorlarni taqqoslash algoritmlarida qoʻllaniladi.