Algoritm murakkabligini baholashda vaqt va xotira talablari murakkablikni baholash

Algoritm murakkabligini baholashda vaqt va xotira talablari
MURAKKABLIKNI BAHOLASH

Algoritmlarning murakkabligi odatda bajarilish vaqti yoki ishlatilgan xotira bilan baholanadi. Ikkala holatda ham, murakkablik kirish ma'lumotlarining hajmiga bog'liq: 100 ta element massivi shunga o'xshash 1000 ga qaraganda tezroq qayta ishlanadi. Shu bilan birga, aniq vaqt bilan bir necha kishi qiziqadi: bu protsessorga bog'liq , ma'lumotlar turi, dasturlash tili va boshqa ko'plab parametrlar. Faqatgina asimptotik murakkablik muhim, ya'ni kirish ma'lumotlarining kattaligi cheksizlikka intilishida murakkablik.

Aytaylik, ba'zi algoritmlar kirish ma'lumotlarining n elementlarini qayta ishlash uchun 4n 3 + 7n shartli operatsiyalarni bajarishi kerak. N ning ortishi bilan ishning umumiy davomiyligi n ning kubiklashi uni 4 ga ko'paytirgandan yoki 7n qo'shgandan ko'ra ko'proq ta'sir qiladi. Keyin ular ushbu algoritmning vaqt murakkabligi O (n 3), ya'ni u kubik bilan kiritilgan ma'lumotlarning hajmiga bog'liqligini aytishadi.

Katta harf O (yoki O-yozuv deb ataladigan) dan foydalanish matematikadan kelib chiqadi, bu erda funktsiyalarning asimptotik harakatlarini taqqoslash uchun ishlatiladi. Rasmiy ravishda O (f (n)) algoritmning ishlash vaqti (yoki ishg'ol qilingan xotira miqdori) kiritilgan ma'lumotlarning hajmiga qarab f (n) ga ko'paytiriladigan ba'zi bir doimiylardan tezroq o'sishini anglatadi.

MISOLLARIO (N) - CHIZIQLI MURAKKABLIK

Bunday murakkablik, masalan, saralanmagan massivdagi eng katta elementni topish algoritmiga ega. Qaysi biri maksimal ekanligini aniqlash uchun massivning barcha n elementlaridan o'tishimiz kerak bo'ladi.

O (LOG N) - LOGARITMIK MURAKKABLIK

Eng oddiy misol - ikkilik qidirish. Agar massiv saralangan bo'lsa, uni yarmiga bo'lish orqali ma'lum bir qiymatga ega ekanligini tekshirishimiz mumkin. Keling, o'rta elementni tekshirib ko'ramiz, agar u istalganidan kattaroq bo'lsa, unda massivning ikkinchi yarmini tashlang - u albatta yo'q. Agar kamroq bo'lsa, unda aksincha - biz dastlabki yarmini tashlaymiz. Va shuning uchun biz ikkiga bo'linishni davom ettiramiz, natijada log n elementlarini tekshiramiz.

O (N 2) - KVADRATIK MURAKKABLIK

Bunday murakkablik, masalan, qo'shilishni saralash algoritmiga ega. Kanonik dasturda bu ikkita ichki ko'chadan iborat: biri butun qatorni bosib o'tish, ikkinchisi esa allaqachon ajratilgan qismdan keyingi element uchun joy topish. Shunday qilib, amallar soni massivning n * n, ya'ni n 2 kattaligiga bog'liq bo'ladi.

Murakkablikning boshqa taxminlari ham mavjud, ammo ularning barchasi bir xil printsipga asoslanadi.

Algoritmning ishlash vaqti umuman kiritilgan ma'lumotlarning hajmiga bog'liq emasligi ham sodir bo'ladi. Keyin murakkablik O (1) bilan belgilanadi. Masalan, massivning uchinchi elementi qiymatini aniqlash uchun elementlarni eslab qolishingiz yoki ular orqali bir necha bor o'tishingiz shart emas. Siz har doim ma'lumotlarni kiritish oqimidagi uchinchi elementni kutishingiz kerak bo'ladi va natijada har qanday ma'lumot uchun hisoblash uchun bir xil vaqt talab etiladigan natija bo'ladi.

Baholash, muhim bo'lganida, xuddi shu tarzda xotiradan amalga oshiriladi. Biroq, algoritmlar kirish ma'lumotlarining hajmi boshqalarga nisbatan kattalashganda sezilarli darajada ko'proq xotiradan foydalanishi mumkin, ammo ular tezroq. Va teskari. Bu hozirgi sharoit va talablar asosida muammolarni hal qilishning eng yaxshi usullarini tanlashga yordam beradi.

Muddati: 2010 yil 8-yanvar

Belgilangan vaqtgacha maqola boshqa loyiha ishtirokchilari tomonidan tahrir qilinmasligi kerak veb-sayt... Tugatgandan so'ng, har qanday ishtirokchi ushbu maqolani o'z xohishiga ko'ra tuzatishga va shablon yordamida ko'rsatilgan ogohlantirishni olib tashlashga haqlidir ((Vazifa)).

Shuningdek qarang ko'rsatmalar Resursdan foydalanish to'g'risida veb-sayt ta'lim jarayonida.

Hisoblash murakkabligi nazariyasi - hisoblash masalasini hal qilish uchun zarur bo'lgan ish hajmini o'rganadigan hisoblash nazariyasining bo'limi.

Muammoni hal qilish uchun foydalaniladigan algoritmdan qat'i nazar, muammoni hal qilish juda ko'p resurslarni talab qilsa, qiyin deb hisoblanadi. Nazariya ushbu intuitiv kontseptsiyani ushbu muammolarni o'rganish uchun matematik hisoblash modellarini joriy qilish va ularni hal qilish uchun zarur bo'lgan vaqt va xotira kabi miqdorlarni aniqlash orqali rasmiylashtiradi. Murakkablikning boshqa o'lchovlari ham mumkin, masalan: xabarlar soni (aloqa murakkabligi), funktsional elementlar davridagi elementlar soni (elektronlar murakkabligi) va protsessorlar soni. Xususan, hisoblashning murakkabligi nazariyasi kompyuterlar qila oladigan va qila olmaydigan narsalarning amaliy chegaralarini belgilaydi.

Hisoblash murakkabligi nazariyasi bilan chambarchas bog'liq algoritmlarni tahlil qilish va hisoblash nazariyasi. Hisoblash murakkabligi nazariyasi va algoritmlarni tahlil qilishning asosiy farqi shundaki, ikkinchisi muammoni hal qilish uchun ma'lum bir algoritm uchun zarur bo'lgan resurslar miqdorini tahlil qilishga bag'ishlangan bo'lsa, birinchisi barcha mumkin bo'lgan algoritmlar haqida umumiyroq savol beradi. bir xil muammoni hal qilish uchun ishlatilishi mumkin bo'lgan muammo. Aniqrog'i, hisoblashning murakkabligi nazariyasi tegishli miqdordagi cheklangan resurslar bilan echilishi mumkin yoki bo'lmasligi mumkin bo'lgan muammolarni tasniflashga urinadi. O'z navbatida, mavjud resurslarga cheklovlar qo'yish, hisoblashning murakkabligi nazariyasini hisoblash nazariyasidan ajratib turadigan narsa: ikkinchisi, qanday resurslarni cheklashsiz, printsipial ravishda, algoritmik tarzda echish mumkinligini so'raydi.

HISOBLASH MUAMMOLARIVAZIFA MISOLLARI

Hisoblash muammolari (vazifalari) ni cheksiz juftlik to'plami sifatida ko'rib chiqish mumkin: (muammoli misol, berilgan misol uchun echim). Hisoblash muammosi uchun kirish satri bu vazifa nusxasini tavsiflovchi satr. Hisoblash muammosi uchun chiqadigan satr, kirish satri bilan tavsiflangan muammo misoli uchun echimning tavsifidir. Masalan, sonning ustunligini tan olish muammosi: muammoli misol - bu uning tub yoki yo'qligini aniqlash zarur bo'lgan son, echim bu raqam tub va "yo'q" bo'lsa, "ha" qatoridir. aks holda. Hisoblash murakkabligi nazariyasi faqat ommaviy muammolarni ko'rib chiqadi, ya'ni. cheksiz vazifa misollari uchun talab majburiydir.

VAZIFA KO'RINISHI

Hisoblash muammolarini ko'rib chiqishda muammo misolining tavsifi alifbo ustidagi satrdir. Qoida tariqasida, alifbo ikkilik (ya'ni, (0,1) to'plam) sifatida qabul qilinadi. Har xil matematik ob'ektlar tegishli ravishda kodlangan bo'lishi kerak. Masalan, butun sonlar ikkilikda ifodalanishi mumkin va grafikalar to'g'ridan-to'g'ri ularning qo'shni matritsalari yoki ikkilik kodlangan qo'shni ro'yxatlar orqali kodlanishi mumkin.

TANIB OLISH VAZIFALARI

E'tirof etish muammolari hisoblash murakkabligi nazariyasining asosiy tadqiqot ob'ektlaridan biridir. E'tirof etish muammosi - bu hisoblashning maxsus turi bo'lib, unga javob "ha" yoki "yo'q" (1 yoki 0) bo'ladi. Tanib olish muammosi barcha kirish satrlari to'plamining ma'lum bir to'plamiga (tiliga) tegishli kirish satrining muammosi sifatida shakllantirilishi mumkin. Muammoning kirish satri mos keladigan tilga tegishli bo'lib, agar ushbu satrga javob ijobiy bo'lsa. Shunday qilib, tanib olish vazifasi - kirish satrining ma'lum bir tilga mansubligini aniqlash vazifasi.

Tanib olish vazifasining misoli. Kirish satri: o'zboshimchalik bilan grafikaning tavsifi. Muammo, berilgan grafikaning ulangan-ulanmaganligini hal qilishda. Bog'langan grafik tili - bu barcha bog'langan grafiklarning tavsiflari to'plamidir. Ushbu tilning aniq ta'rifini olish uchun grafikalar qanday qilib ikkilik qator sifatida kodlanishini hal qilishingiz kerak.

VAZIFALARNI QIDIRISH

Qidiruv vazifasi hisoblash vazifasi bo'lib, unda chiqish qiymati tanib olish vazifasidan ko'ra murakkabroq bo'ladi (ya'ni bu shunchaki "ha" yoki "yo'q" emas).

Qidiruv muammosiga misol - sayohat qilayotgan sotuvchi muammosi. Sayohat qiluvchi sotuvchi muammosi (sayohat qiluvchi sotuvchi - sayohat qiluvchi sotuvchi) - bu eng mashhur kombinatoriya optimallashtirish muammolaridan biri. Vazifa shundan iboratki, belgilangan shaharlardan kamida bir marta o'tgan shaharga qaytish bilan eng foydali marshrutni topish. Muammo sharoitida marshrutning rentabellik mezonlari (eng qisqa, eng arzon, yig'ma mezon va boshqalar) va mos keladigan matritsalar, xarajatlar va boshqalar ko'rsatilgan, qoida tariqasida marshrut har bir shahar orqali faqat bir marta o'tishi kerak - bu holda Hamilton davrlari orasida tanlov qilinadi. Kirish satri: vaznli (ya'ni qirralarda son bilan belgilangan) grafika tavsifi. Chiqish qatori sayohatchining eng maqbul marshruti tavsifidir.

Tanib olish vazifalari va qidiruv vazifalari o'rtasida juftlik munosabatlari mavjud. Qidiruv muammosi tanib olish muammosi sifatida shakllantirilishi mumkin. Masalan, "ikkita sonni ko'paytirish" izlash muammosi uchun mos keladigan juftlik bilan aniqlash masalasi A × B \u003d C munosabati qondirilishi uchun uchlik (A, B, C) to'plami sifatida ifodalanishi mumkin.

MURAKKABLIKNI O'LCHASH

Hisoblash murakkabligi nazariyasi algoritmlarning ishlash ko'rsatkichlarini taqqoslash, kirish va chiqish hajmiga qarab ularning xatti-harakatlarini (bajarilish vaqti, kerakli xotira miqdori va boshqalarni) aniq tavsiflash zaruriyatidan kelib chiqqan.

Algoritm tomonidan masalaning aniq bir misolini hal qilish uchun sarflangan elementar operatsiyalar soni nafaqat kiritilgan ma'lumotlarning hajmiga, balki ma'lumotlarning o'ziga ham bog'liqdir. Masalan, kiritish ma'lumotlari allaqachon tartiblangan bo'lsa, qo'shishni tartiblash algoritmining operatsiyalari soni ancha kam. Bunday qiyinchiliklarni oldini olish uchun eng yomon holatda algoritmning vaqt murakkabligi tushunchasini ko'rib chiqing.

Algoritmning vaqt murakkabligi (eng yomon holatda) - bu kirish va chiqish ma'lumotlarining o'lchamlari, belgilangan o'lchamdagi masalaning misolini hal qilish uchun algoritm tomonidan bajariladigan elementar operatsiyalarning maksimal soniga teng. Chiqish kattaligi kattaligi kattaligidan oshmaydigan yoki mutanosib bo'lgan muammolarda vaqt murakkabligi faqat kirish ma'lumotlari hajmining funktsiyasi sifatida qaralishi mumkin.

Eng yomon holatda vaqt murakkabligi tushunchasiga o'xshab, eng yaxshi holatda algoritmning vaqt murakkabligi tushunchasi aniqlanadi. Shuningdek, ular algoritmning o'rtacha ish vaqti tushunchasini, ya'ni algoritmning ishlash vaqtining matematik kutilishini ko'rib chiqadilar. Ba'zan ular sodda qilib aytadilar: "Algoritmning vaqt murakkabligi" yoki "Algoritmning ishlash vaqti", ya'ni algoritmning vaqt murakkabligini eng yomon, eng yaxshi yoki o'rtacha holatda (kontekstga qarab) anglatadi.

Vaqtning murakkabligi bilan taqqoslaganda, algoritmning fazoviy murakkabligi aniqlanadi, faqat bu erda ular elementar operatsiyalar soni haqida emas, balki ishlatiladigan xotira miqdori haqida gapirishadi.

Algoritmning vaqt murakkabligi funktsiyasini ba'zi hollarda aniq aniqlash mumkinligiga qaramay, aksariyat hollarda uning aniq qiymatini izlash mantiqsiz. Haqiqat shundaki, birinchidan, vaqt murakkabligining aniq qiymati elementar operatsiyalarning ta'rifiga bog'liq (masalan, murakkablik arifmetik operatsiyalar yoki Turing mashinasida bajariladigan operatsiyalar sonida o'lchanishi mumkin), ikkinchidan, kirish ma'lumotlarining kattaligi, doimiy omil va atamalarning hissasi, ishlashning aniq vaqti uchun ifodada paydo bo'ladigan pastki buyruqlar juda ahamiyatsiz bo'ladi.

Katta hajmdagi kirish ma'lumotlarini ko'rib chiqish va algoritmning ishlash vaqtining o'sish tartibini baholash algoritmning asimptotik murakkabligi tushunchasiga olib keladi. Bunday holda, asimptotik murakkabligi pastroq bo'lgan algoritm barcha kirish ma'lumotlari uchun samaraliroq bo'ladi, ehtimol kichik o'lchamdagi ma'lumotlar bundan mustasno.

Murakkablik hisob-kitoblar amalga oshiriladigan hisoblash modeli asosida aniqlanadi.

HISOBLASH MODELLARI

Hisoblashning turli xil modellari mavjud: Post mashinasi, Minskiy mashinasi, lambda hisobi, qisman rekursiv funktsiyalar, oddiy Markov algoritmlari, o'zboshimchalik bilan xotiraga kirish imkoniyatiga ega mashinalar (RAM mashinalari) va boshqalar. Faqat eng mashhur hisoblash modeli - Turing mashinasini eslatib o'tamiz. .

TURING MASHINASI

Turing mashinasi (MT) mavhum ijrochi (mavhum hisoblash mashinasi). Algoritm tushunchasini rasmiylashtirish uchun 1936 yilda Alan Turing tomonidan taklif qilingan.

Turing mashinasi - bu cheklangan davlat mashinasining kengaytmasi va Cherkov-Turing tezisiga ko'ra, hisoblashning har bir bosqichi bo'lgan bosqichma-bosqich hisoblash jarayonini qandaydir tarzda amalga oshiradigan boshqa barcha ijrochilarga taqlid qilishga qodir (o'tish qoidalarini ko'rsatgan holda). juda oddiy.

Tyuring mashinasi tarkibiga ikkala yo'nalishda ham cheksiz lenta (bir nechta cheksiz lentalarga ega bo'lgan Turing mashinalari mumkin), hujayralarga bo'lingan va ko'plab holatlardan birida bo'lishi mumkin bo'lgan boshqarish moslamasi kiradi. Boshqarish moslamasining mumkin bo'lgan holatlari soni cheklangan va aniq ko'rsatilgan.

Boshqarish moslamasi lenta bo'ylab chapga va o'ngga siljishi, lenta katakchalariga ba'zi cheklangan alifbo belgilarini o'qishi va yozishi mumkin. Kassetaning barcha katakchalarini to'ldiradigan maxsus bo'sh belgi ajratilgan, ulardan faqat kirish ma'lumotlari yozilgan (sonli raqam) hujayralar bundan mustasno.

Nazoratchi ushbu Turing mashinasi tomonidan amalga oshirilgan algoritmni ifodalovchi o'tish qoidalariga muvofiq ishlaydi. Har bir o'tish qoidasi mashinaga joriy holatga va joriy katakda kuzatilgan belgiga qarab, ushbu katakchada yangi belgi yozish, yangi holatga o'tish va bitta katakchani chapga yoki o'ngga siljitishni buyuradi. Tyuring mashinasining ba'zi holatlarini terminal sifatida belgilash mumkin va ularning har biriga o'tish ishning tugashi, algoritmning to'xtashi deganidir.

Jadvaldagi holat va chiziq belgilarining har bir kombinatsiyasiga bitta qoidadan ko'pi mos kelmasa, Turing mashinasi deterministik deb nomlanadi. Agar ikkita yoki undan ortiq ko'rsatmalar mavjud bo'lgan juftlik bo'lsa (chiziq belgisi - holat), bunday Turing mashinasi deterministik emas deb nomlanadi.

Turing mashinasi modeli har xil kengaytmalarni tan oladi. Biz Turing mashinalarini o'zboshimchalik bilan lentalari va ko'p o'lchovli lentalari bilan har xil cheklovlarga ega deb hisoblashimiz mumkin; tasodifiy manbadan foydalanadigan mashinalar.

Turing mashinasi murakkablik nazariyasining asosiy hisoblash modellaridan biridir.

QIYINCHILIK DARSLARI

Qiyinchilik sinflari - bu hisoblashning murakkabligi bo'yicha taxminan bir xil bo'lgan hisoblash muammolari to'plami. Til murakkabligi va funktsional murakkablik sinflari mavjud. Tillarning murakkablik sinfi - taxmin qilish uchun bir xil miqdordagi resurslardan foydalanadigan predikatlar to'plami (so'zni kiritish sifatida qabul qiladigan va 0 yoki 1 javobni qaytaradigan funktsiyalar). Funktsional murakkablik tushunchasi o'xshash, faqat predikatlar to'plami emas, balki funktsiyalar to'plamidir. Murakkablik nazariyasida, sukut bo'yicha, murakkablik sinfi tillarning murakkabligi sinfidir. Murakkablik sinfining odatiy ta'rifi quyidagicha:

X murakkablik sinfi - Turing mashinalari tomonidan hisoblab chiqiladigan va hisoblash uchun O (f (n)) resurslaridan foydalanadigan P (x) predikatlar to'plami, bu erda n - x so'zining uzunligi.

Hisoblash vaqti (Turing mashinasining ishchi tsikllari soni) yoki ish maydoni (ish paytida lentada ishlatiladigan kataklar soni) odatda resurs sifatida qabul qilinadi. Predikatlar tomonidan ma'lum bir sinfdan tanilgan tillar (ya'ni, predikat qaytaradigan so'zlar to'plami) ham shu sinfga mansub deb nomlanadi.

Bundan tashqari, ko'plab sinflarni matematik mantiq yoki o'yin nazariyasi nuqtai nazaridan ham tavsiflash mumkin.

Sinflar odatda katta harflar bilan belgilanadi. S sinfiga (ya'ni, to`ldiruvchisi S ga tegishli bo`lgan tillar sinfiga) to`ldiruvchi ko-C bilan belgilanadi.

Har bir sinf uchun "eng qiyin" vazifalar toifasi mavjud. Bu shuni anglatadiki, sinfdan har qanday topshiriq shunday vazifaga keltiriladi va vazifaning o'zi sinfda bo'ladi. Bunday vazifalar ma'lum bir sinf uchun to'liq topshiriqlar deb nomlanadi.

P SINF

P klassi (inglizcha polinomdan) - kirish uzunligi bo'yicha vaqt polinomida deterministik Turing mashinasida echilishi mumkin bo'lgan tan olish muammolari to'plami. Xuddi shu tarzda, qidiruv vazifalari uchun FP klassi (inglizcha funktsional polinomdan) aniqlanadi.

Rasmiy ravishda, kirish lentasiga berilgan kirish alifbosidan berilgan so'zni hisoblab chiqadigan deterministik Turing mashinalarini ko'rib chiqing. Belgilangan kirish so'zi uchun Turing mashinasining ishlash vaqti x - Turing mashinasining boshidan to to'xtashigacha ishlaydigan tsikllari soni. Ba'zi Turing mashinalari tomonidan hisoblangan funktsiyaning murakkabligi kirish so'zining uzunligiga bog'liq bo'lgan va sobit uzunlikdagi barcha kirish so'zlari uchun mashinaning maksimal ishlash vaqtiga teng bo'lgan funktsiyadir:

.

Agar funktsiya uchun bo'lsa f Turing mashinasi mavjud M shunday qilib, ba'zi raqamlar uchun v va etarlicha katta n, keyin ular FP sinfiga tegishli yoki vaqt ichida polinom deyishadi.

P klassi hisoblashning murakkabligi nazariyasining asoslaridan biridir.

NP KLASSI

NP klassi (inglizcha determinatsiyalanmagan polinomdan) tan olish muammolari to'plami bo'lib, ularni hal qilish vaqti kirish ma'lumotlari hajmiga katta bog'liqdir; Shu bilan birga, kiritilgan qiymatlarning tavsifi bilan bir qatorda ba'zi qo'shimcha ma'lumotlarni (qaror guvohi) olgan algoritm mavjud bo'lib, tezda (o'lchamdagi polinomdan oshmagan vaqt ichida) ma'lumotlar) muammoni hal qilish.

Rasmiy ravishda, agar P sinfidan (ya'ni polinom vaqtida hisoblab chiqiladigan) ikki o'rinli predikat (R, x, y) mavjud bo'lsa, L til NP sinfiga tegishli deyiladi va har qanday x so'z uchun n uzunligi "x" L ga tegishli "shartga tengmi" R (x, y) ga teng uzunlik p (n) dan kam ". Y so'zi L tiliga mansub x ning guvohi deb ataladi. Shunday qilib, agar bizda tilga tegishli so'z va cheklangan uzunlikdagi boshqa guvoh so'z bo'lsa (uni topish qiyin bo'lishi mumkin bo'lsa), unda tezda bunga amin bo'lishimiz mumkin. x haqiqatan ham L ga tegishli bo'lib, NPga tegishli har qanday muammoni eksponent vaqt ichida p (n) dan kichik uzunlikdagi barcha guvohlarni sanab o'tish yo'li bilan hal qilish mumkin.

NP dan olingan muammoga misol: "Chiziqli tengsizliklar tizimiga butun sonli echimning mavjudligi" ni tanib olish muammosi. Guvoh - bu tengsizliklar tizimining echimi. Polinom vaqtida guvohning echimi mos kelishini tekshirish oson.

NP sinfiga P klassi kiradi.

OCHIQ MUAMMOLAR

Hisoblash murakkabligi nazariyasida ko'plab hal qilinmagan muammolar mavjud, asosan ular ma'lum bir murakkablik sinflarini ajratish yoki uyalash masalalariga tegishli. Ana shunday savollardan biri P va NP sinflarining tengligi muammosidir.

P VA NP SINFLARINING TENGLIGI MUAMMOSI

Oxir oqibat, P va NP sinflarining tengligi muammosi quyidagicha: agar savolga ijobiy javobni tezda tasdiqlash mumkin bo'lsa (polinom vaqtida), bu savolga javob tezda topilishi mumkinmi (polinom vaqtida) )?

Quyidagi xulosa darhol P va NP sinflarining ta'rifidan kelib chiqadi:. Biroq, hozirgi kunga qadar ushbu qo'shilishning zo'ravonligi haqida hech narsa ma'lum emas, ya'ni. NPda yotadigan, ammo Pda yotmaydigan algoritm mavjudmi, agar bunday algoritm mavjud bo'lmasa, u holda NP sinfiga tegishli bo'lgan barcha masalalarni polinom vaqt ichida echish mumkin, bu hisoblash nuqtai nazaridan katta foyda keltiradi. Hozirgi kunda eng qiyin NP-muammolarni (NP-to'liq masalalar deb ataladigan) eksponent vaqt ichida echish mumkin, bu deyarli har doim qabul qilinishi mumkin emas.

Ushbu ikki sinfning tengligi masalasi nazariy informatika sohasidagi eng qiyin ochiq muammolardan biri hisoblanadi. Hozirgi kunda ko'pgina matematiklar bu sinflar teng emas deb hisoblashadi. Kley Matematik Instituti ushbu muammoni Mingyillik muammolari ro'yxatiga kiritdi va uni hal qilgani uchun 1 million dollar mukofot puli taqdim etdi.

ADABIYOTGehry M., Johnson D. Hisoblash mashinalari va hal qilinmaydigan muammolar. "Mir" nashriyoti 1982 yilda. - 420 p. Amerikalik olimlarning monografiyasi diskret optimallashtirish, matematik dasturlash, algebra va avtomatlar nazariyasida yuzaga keladigan murakkab (shu jumladan NP-hard) kombinatoriya muammolarini misollar bilan hal qilishga bag'ishlangan.Kormen, Tomas H.; Leyzerson, Charlz I.; Rivest, Ronald L.; Shtayn, Kliford algoritmlari: Qurilish va tahlil, 2-nashr \u003d Algoritmlarga kirish ikkinchi nashr. - M.: "Uilyams", 2005. -

Xuddi shu muammoni hal qilish uchun ko'pincha bir nechta algoritmni ishlab chiqish mumkin. Shu munosabat bilan savol tug'iladi: algoritmlarning qaysi biri "yaxshiroq"?

Ko'pgina hollarda, "yaxshiroq", aftidan, xuddi shu kirish ma'lumotlaridan foydalanib, muammolarni hal qilishga keladigan, kamroq hisoblash resurslarini (xotira va vaqt) sarflaydigan algoritm. Bu, albatta, bo'sh fikr. Keyinchalik qat'iy fikrlash uchun biz bir nechta tushunchalarni kiritamiz.

Algoritmni hisoblash jarayoni bu ba'zi bir kirish ma'lumotlari uchun algoritmning bajarilishidan o'tgan qadamlar ketma-ketligi.

Algoritmning o'zi va ushbu algoritm tomonidan yaratilgan hisoblash jarayoni o'rtasidagi farqni tushunish muhimdir. Birinchisi faqat tavsif ikkinchi.

Algoritmning vaqt murakkabligi - bu ba'zi bir kirish ma'lumotlari uchun algoritmni hisoblash jarayonini yakunlash uchun zarur bo'lgan vaqt ((T \\)).

Amal qilish muddati aniq ijrochiga bog'liqligi aniq. Aytaylik, elektron kalkulyator va superkompyuter har xil vaqtda bir xil algoritmni boshqarishi mumkin.

Biroq, vaqtni \\ (T \\) elementar harakatlar soni \\ (k \\) va boshlang'ich harakatlarning o'rtacha bajarilish vaqti (\\ t \\) orqali ifodalash mumkin:

Bundan tashqari, \\ (k \\) xususiyatdir eng algoritm, va \\ (t \\) - ijrochining xususiyati.

\\ (T \\) berilgan ijrochi uchun doimiy deb qaralishi mumkinligi sababli, odatda algoritmlarning murakkabligi doimiy koeffitsientgacha baholanadi. Boshqacha qilib aytganda, algoritmning murakkabligi taxmin qilinadi o'sish tartibi.

O'sish tartibi Ijobiy aniq funktsiya \\ (g (x) \\) ning o'sish tartibi \\ (f (x) \\) (yozilgan \\ (g (x) \u003d \\ mathcal (O) (f (x)) \\)) bo'lsa \\ (\\ mavjud c\u003e 0: \\: \\ for all x\u003e x_0, \\, g (x) \\ leq c f (x) \\).

Kiritilgan ma'lumotlarga qarab, algoritm turli vaqtlarda ishlashi mumkin. Odatda taxmin qilinadi o'rtacha murakkablik va murakkablik eng yomoni... Bunga bog'liqlik ham mavjud miqdor ma'lumotlarni kiritish \\ (n \\). Odatda \\ (n \\) ning o'sish tartibi baholanadi.

Masalan, ma'lumotlarni o'qish va ularni xotirada massiv sifatida saqlash murakkablikka ega bo'ladi \\ (\\ mathcal (O) (n) \\), yoki chiziqli murakkablikva matritsani ko'paytirish allaqachon kub \\ (\\ mathcal (O) (n ^ 3) \\).

Algoritmning vaqt murakkabligidan tashqari, u ham muhimdir fazoviy algoritmning murakkabligi.

Algoritmning fazoviy murakkabligi bu son qo'shimcha algoritm ishlashni talab qiladigan xotira \\ (S \\). Kirish ma'lumotlarini saqlash uchun zarur bo'lgan xotira \\ (D \\) \\ (S \\) tarkibiga kirmaydi.

\\ (S \\) odatda ijro etuvchiga ham bog'liq. Masalan, agar ikkita ijro birligi mos ravishda 4 va 8 baytli butun sonlarni qo'llab-quvvatlasa, u holda 8 baytli butun sonlar uchun algoritmning fazoviy murakkabligi 4 baytli tamsayılardan ikki baravar katta bo'ladi. Shuning uchun fazoviy murakkablik xuddi shu o'sish tartibida baholanadi.

ALGORITM MURAKKABLIGI DARSLARI

Aniq qiyinchilik darslari: Bu o'xshash qiyinchiliklarga ega bo'lgan toifalar.

Quyidagi asosiy qiyinchilik sinflari ajratiladi:

DTIME A Turing mashinasi muammoning echimini cheklangan vaqt ichida topadi (qadamlar soni). Algoritmning asimptotikasi ko'pincha ko'rsatiladi, shuning uchun aytaylik, agar ish vaqtining o'sish tartibi \\ (T (n) \u003d \\ mathcal (O) (f (n)) \\) bo'lsa, u holda \\ (DTIME (f (n)) \\) ko'rsatiladi. P Turing mashinasi muammoning echimini polinom vaqtida (qadamlar soni) topadi, ya'ni. \\ (T (n) \u003d \\ mathcal (O) (n ^ k) \\), qaerda \\ (k \\ in \\ mathbb (N) \\). \\ (P \u003d DTIME (n ^ k) \\) EXPTIME Turing mashinasi muammoning echimini eksponent vaqt (qadamlar soni) da topadi, ya'ni. \\ (T (n) \u003d \\ mathcal (O) (2 ^ (n ^ k)) \\) $, bu erda \\ (k \\ in \\ mathbb (N) \\). \\ (EXPTIME \u003d DTIME (2 ^ (n ^ k)) \\). DSPACE Turing mashinasi cheklangan miqdordagi qo'shimcha xotira (hujayralar) yordamida muammoning echimini topadi. Algoritmning asimptotikasi ko'pincha aniqlanadi, masalan, xotira sarfining o'sish tartibi \\ (S (n) \u003d \\ mathcal (O) (f (n)) \\) bo'lsa, u holda \\ (DSPACE (f (n) )) \\) ko'rsatiladi. L Turing mashinasi logaritmik fazoviy murakkablik, ya'ni. \\ (S (n) \u003d \\ mathcal (O) (\\ log n) \\)... \\ (L \u003d DSPACE (\\ log n) \\). PSPACE Turing mashinasi polinom fazoviy murakkabligi, ya'ni \\ (S (n) \u003d \\ mathcal (O) (n ^ k) \\), masalan, \\ (k \\ in \\ mathbb (N) \\) masalasiga echim topadi. ). \\ (PSPACE \u003d DSPACE (n ^ k) \\). EXPSPACE Turing mashinasi eksponent fazoviy murakkablik, ya'ni. \\ (S (n) \u003d \\ mathcal (O) (2 ^ (n ^ k)) \\), bu erda \\ (k \\ in \\ mathbb (N) \\). \\ (EXPSPACE \u003d DSPACE (2 ^ (n ^ k)) \\).

Bundan tashqari, kontseptsiya asosida ishlaydigan murakkablikning nazariy sinflari mavjud aniqlanmagan Turing mashinalari (TMT). Ularning ta'riflari yuqorida aytilganlarga to'g'ri keladi, Tyuring mashinasi NMT bilan almashtiriladi va ismlar N prefiksiga ega (masalan, NP), NTIME va NSPACE tashqari, D o'rnini N ga almashtiradi.

NMT - bu ishning tamoyillari nuqtai nazaridan MTga o'xshash, har bir holat uchun har xil bo'lishi mumkin bo'lgan farq bilan, xuddi nazariy qurilish. biroz mumkin bo'lgan harakatlar. Shu bilan birga, NMT har doim mumkin bo'lgan harakatlar orasidan eng kam qadamlar sonida echimga olib keladigan harakatni tanlaydi. Bunga teng ravishda, HMT hisob-kitoblarni amalga oshiradi hammasidan eng kam sonli bosqichlarda echimga olib boradigan filialni tanlaydi va tanlaydi.

Ba'zan kvant kompyuterlari HMT dasturlari ekanligini eshitishingiz mumkin. Ba'zi hollarda bu haqiqat bo'lib tuyulishi mumkin bo'lsa-da, umuman HMT kvant kompyuteriga qaraganda kuchliroq tizimdir.

Ma'lumki \\ (P \\ subseteq NP \\ subseteq PSPACE \\ subseteq EXPTIME \\ subseteq NEXPTIME \\ subseteq EXPSPACE \\)

Bundan tashqari, \\ (P \\ subsetneq EXPTIME \\), \\ (NP \\ subsetneq NEXPTIME \\), \\ (PSPACE \\ subsetneq EXPSPACE \\)

Bundan tashqari, agar \\ (P \u003d NP \\) bo'lsa, unda \\ (EXPTIME \u003d NEXPTIME \\) ekanligi ma'lum.

P va NP tengligi masalasi zamonaviy kompyuter fanining hal qilinmagan asosiy muammolaridan biridir.

ALGORITM MISOLLARI

Bu erda oddiy algoritmlarga bir nechta misollar keltirilgan va ularning murakkabligini ko'rib chiqing.

KO'RSATKICH

Ushbu algoritm qadimgi Hindistonda bizning davrimizgacha tasvirlangan va haqiqiy sonning tabiiy kuchini \\ (n \\) hisoblashda foydalanilgan \\ (x \\)

\\ (N \\) ni ikkilik yozuvda yozingUshbu yozuvda 1-ning har birini juftlik bilan KX, har 0-ni K harfi bilan almashtiringEng chap KX juftligini kesib olingOlingan satrni chapdan o'ngga o'qish, K harfi bilan uchrashish, natijani kvadratga solish va X harfini uchratish natijasida natijani x ga ko'paytiring. Boshida natija x ga teng.

Ushbu algoritmda biz ko'paytirish operatsiyalari sonini ikkitomonlama tasvirlashdagi raqamlar soniga teng \\ (n \\), eng yomoni esa \\ (2 (n-1) \\) ga egamiz. Har holda, vaqtning murakkabligi.

Algoritmni samarali amalga oshirishda qo'shimcha xotira deyarli talab qilinmaydi va u kirish ma'lumotlariga bog'liq emas, shuning uchun fazoviy murakkablik \\ (S (n) \u003d \\ mathcal (O) (1) \\) dir.

Shuni ta'kidlash kerakki, yanada samarali algoritmlar mavjud. Ammo \\ (\\ mathcal (O) (n) \\) ko'paytirish operatsiyalarini talab qiladigan "sodda" dastur bilan taqqoslaganda, bu algoritm nisbatan samarali.

BUTUNLIKNI KO'PAYTIRISH

Ushbu ko'paytirish algoritmi ba'zan Qadimgi Misrgacha ma'lum bo'lgan bo'lsa-da, rus yoki dehqon deb nomlanadi.

Birinchi omil ketma-ket ikkiga ko'paytiriladi, ikkinchisi esa butunlay 2 ga bo'linadi. Natijalar ikki ustunga yozilib, ikkinchisi 1 ga teng bo'ladi.

Ko'paytirish natijasi birinchi ustundagi raqamlarning yig'indisidir, qarama-qarshi ikkinchi ustundagi toq sonlar.

Butun sonni bo'lishish va 2 ga ko'paytirishni siljitish yo'li bilan amalga oshirish mumkin bo'lganligi sababli, ushbu algoritm \\ (2 \\ log_2 n \\) siljish operatsiyalarini beradi, bu erda \\ (n \\) ikkita sonning eng kichigi. Eng yomon holatda, \\ (\\ log_2 n - 1 \\) qo'shish operatsiyalari ham olinadi. Baribir, vaqtning murakkabligi \\ (T (n) \u003d \\ mathcal (O) (\\ log n) \\).

Algoritmni samarali amalga oshirish uchun qo'shimcha xotira deyarli talab qilinmaydi va u kiritilgan ma'lumotlarga bog'liq emas, shuning uchun \\ (S (n) \u003d \\ mathcal (O) (1) \\)

Shunga qaramay, yanada samarali algoritmlar mavjudligini ta'kidlash kerak. Biroq, \\ (\\ mathcal (O) (n) \\) qo'shimcha operatsiyalarini talab qiladigan "sodda" dastur bilan taqqoslaganda, ushbu algoritm nisbatan samarali.

MISOL

23 ni 43 ga ko'paytiring.

Ikkinchi omil sifatida 23 ni olaylik.

4323g'alati8611g'alati1725g'alati34426881g'alati

Natija \\ (43 + 86 + 172 + 688 \u003d 989 \\)

Biz 10 ta smenali operatsiya va 4 ta operatsiyani oldik. Ma'lumot uchun, \\ (\\ log_2 (23) \\ taxminan 4.52 \\)