• Kvazilinear vaqt Algoritm kvazizikli vaqtda ishlaydi, deyiladi, agar T ( n ) = O ( n jurnal k n )
  • Algoritmning vaqt murakkabligini baholash. Algoritmlar murakkabligi funksiyalarining turlari Doimiy vaqt




    Download 95,56 Kb.
    bet3/16
    Sana15.05.2024
    Hajmi95,56 Kb.
    #235940
    1   2   3   4   5   6   7   8   9   ...   16
    Bog'liq
    Algoritmning vaqt murakkabligini baholash. Algoritmlar murakkabl

    Lineer vaqt
    chiziqli vaqt, yoki O ( nagar uning murakkabligi O bo'lsa ( n). Norasmiy ravishda, bu etarli darajada katta kirish hajmi uchun ish vaqti kirish hajmi bilan chiziqli ravishda oshib borishini anglatadi. Masalan, ro'yxatning barcha elementlarini jamlaydigan protsedura ro'yxat uzunligiga proportsional vaqtni oladi. Ushbu tavsif to'liq aniq emas, chunki ish vaqti aniq proportsionallikdan sezilarli darajada farq qilishi mumkin, ayniqsa kichik qiymatlar uchun. n.
    Chiziqli vaqt ko'pincha algoritmning kerakli atributi sifatida qaraladi. (deyarli) chiziqli ish vaqti yoki undan yuqori bo'lgan algoritmlarni yaratish uchun ko'plab tadqiqotlar o'tkazildi. Ushbu tadqiqotlar dasturiy ta'minot va apparat yondashuvlarini o'z ichiga oladi. Uskunani bajarish holatida, standart hisoblash modellarida matematik jihatdan hech qachon chiziqli bajarish vaqtiga erisha olmaydigan ba'zi algoritmlar chiziqli vaqtda ishlashi mumkin. Ushbu maqsadga erishish uchun parallellikdan foydalanadigan ba'zi apparat texnologiyalari mavjud. Masalan, assotsiativ xotira. Ushbu chiziqli vaqt tushunchasi Boyer-Mur algoritmi va Ukkonen algoritmi kabi qatorlarni taqqoslash algoritmlarida qo'llaniladi.
    Kvazilinear vaqt
    Algoritm kvazizikli vaqtda ishlaydi, deyiladi, agar T(n) = O ( n jurnal k nba'zi doimiy uchun k... Chiziqli-logarifmik vaqt bilan alohida holat k= 1. Zaif-O belgilaridan foydalanilganda, bu algoritmlar Õ ( n). Kvazilinear vaqt algoritmlari ham o ( n 1 + e) ​​har qanday e> 0 uchun va har qanday polinomdan tezroq ishlaydi n
    Yuqorida aytib o'tilgan chiziqli-logarifmik algoritmlarga qo'shimcha ravishda, kvaziziiqli vaqtda ishlaydigan algoritmlarga quyidagilar kiradi:

    • O'z joyida birlashtirish tartibi, O ( n jurnal 2 n)

    • Tez tartiblash, O ( n jurnal n), ehtimolli versiyada eng yomon holatda chiziqli-logarifmik bajarilish vaqti mavjud. Mumkin bo'lmagan versiyada o'rtacha qiyinchilikni o'lchash uchun chiziqli jurnalning ishlash vaqti mavjud.

    • Uyumni tanlash, O ( n jurnal n), birlashma tartiblash, introsort, ikkilik daraxt tartibi, silliq tartiblash, solitaire turi, va hokazo. eng yomoni

    • Tez Furye o'zgarishi, O ( n jurnal n)

    • Monge matritsalarini hisoblash, O ( n jurnal n)


    Download 95,56 Kb.
    1   2   3   4   5   6   7   8   9   ...   16




    Download 95,56 Kb.

    Bosh sahifa
    Aloqalar

        Bosh sahifa



    Algoritmning vaqt murakkabligini baholash. Algoritmlar murakkabligi funksiyalarining turlari Doimiy vaqt

    Download 95,56 Kb.