[Powered by Google Translate] Вы, напэўна, чулі, як людзі кажуць аб хуткім і эфектыўным алгарытме для выканання вашай канкрэтнай задачы, але што менавіта гэта значыць для алгарытму, каб быць хуткім ці эфектыўным? Ну, гэта не гаворыць аб вымярэння ў рэальным часе, як секунд ці хвілін. Гэта таму, што кампутарная тэхніка і праграмнага забеспячэння значна вар'іравацца. Мая праграма можа працаваць павольней, чым ваш, таму што я бягу яго на старым кампутары, ці таму што я, аказваецца, гуляе онлайн-гульня відэа У той жа час, якое коробления ўсю маю памяць, ці я можа быць запушчана мая праграма з дапамогай розных праграм , Які мае зносіны з машынай па-рознаму на нізкім узроўні. Гэта ўсё роўна, што параўноўваць яблыкі і апельсіны. Проста таму, што мой павольны кампутар займае больш часу, чым ваш аддаць адказ не азначае, што ў вас ёсць больш эфектыўны алгарытм. 

Такім чынам, паколькі мы не можам напрамую параўнаць час працы праграмы на працягу секунд ці хвілін, як мы можам параўнаць 2 розных алгарытмаў незалежна ад іх апаратнай або праграмнай асяроддзі? Каб стварыць больш універсальны спосаб вымярэння алгарытмічнай эфектыўнасці, навукоўцаў-кампутарнікаў і матэматыкаў распрацавалі канцэпцыі для вымярэння асімптатычнай складанасці праграмы і пазначэнняў называецца "Вялікі Ohnotation" Для апісання гэтага. Фармальнае вызначэнне з'яўляецца тое, што функцыя F (X) працуе на парадак д (х) калі існуе некаторы (х) значэнні х і ₀ некаторая канстанта, C, для якой F (X) менш або роўная што пастаяннае разы д (х) для ўсіх х больш х ₀. 

Але не палохае фармальнае вызначэнне. Што гэта на самай справе азначае менш тэарэтычнай пункту гледжання? Ну, гэта ў асноўным спосаб аналізу як хутка час выканання праграмы расце асімптатычна. Гэта значыць, як памер ўваходу павялічваецца да бясконцасці, Скажам, вы сартавання масіву памерам 1000 па параўнанні з масіў памеру 10. Як выканання вашай праграмы растуць? Напрыклад, уявіце сабе падліку колькасці сімвалаў у радку самы просты спосаб  пешшу праз усю радок Ліст за лістом і дадання 1 да лічыльніку для кожнага знака. Гэты алгарытм, як кажуць, працуюць у лінейным часу па адносінах да колькасці знакаў, 'N' у радку. Карацей кажучы, ён працуе ў O (N). Чаму гэта адбываецца? Ну, пры такім падыходзе, час, неабходнае прайсці ўсю радок прапарцыйная колькасці знакаў. Падлік колькасці знакаў у 20-знакавай радкі збіраецца ўзяць у два разы даўжэй, як гэта мае для падліку знакаў у 10-знакавай радкі, таму што вы павінны глядзець на ўсе знакі і кожны знак займае столькі ж часу, каб глядзець на. Па меры павелічэння колькасці знакаў, серада выканання будзе лінейна ўзрастаць з уваходнай даўжыні. 

А цяпер уявіце, калі вы вырашыце, што лінейнае час, Аб (п), проста не быў досыць хуткі для Вас? Можа быць, вы захоўвання велізарных радкоў, і вы не можаце дазволіць сабе дадатковы час, якое запатрабуецца , Каб абыйсці ўсе іх характары лічачы адзін-на-адзін. Такім чынам, вы вырашылі паспрабаваць нешта іншае. Што рабіць, калі здарылася б ўжо захоўваюцца колькасць сімвалаў у радку, скажам, у зменную пад назвай «Лена», на раннім этапе праграмы, перш чым вы нават захоўваецца самы першы знак у радку? Тады ўсё што вам прыйдзецца зрабіць цяпер, каб даведацца даўжыню радка, гэта праверыць, што значэнне зменнай. Вам не давядзецца глядзець на саму радок на ўсіх, і доступу да значэння зменнай, як лён лічыцца асімптатычна пастаяннае час аперацыі, або O (1). Чаму гэта адбываецца? Ну, памятаеце, што асімптатычнай складанасць азначае. Як выканання змяненняў, як памер Вашага ўваходу расце? 

Скажыце, што Вы спрабавалі атрымаць лік знакаў у радку больш. Ну, гэта не мае значэння, наколькі вялікі Вы робіце радкі, нават мільён знакаў, ўсё, што Вы павінны былі б зрабіць, каб знайсці даўжыню радка з гэтым падыходам, , Каб зачытаць значэнне зменнай даўжыня, якія вы ўжо зрабілі. Даўжыні ўваходу, гэта значыць даўжыня радка, якую вы спрабуеце знайсці, не ўплывае на ўсіх, як хутка ваша праграма працуе. Гэтая частка праграмы будзе працаваць аднолькава хутка на адзін радок сімвалаў і тысяча-знакавай радкі, і менавіта таму гэтая праграма будзе называцца працуе ў пастаянным часу ў дачыненні да памеру ўваходных дадзеных. 

Вядома, ёсць недахоп. Вы марнуеце дадатковае прастору памяці кампутара захоўвання зменнай і дадатковы час, неабходнае вам зрабіць фактычнага захоўвання зменнай, але справа да гэтага часу стаіць, высветліць, як доўга ваша радок была не залежыць ад даўжыні радка на ўсіх. Такім чынам, ён працуе ў O (1) або пастаяннай часу. Гэта, вядома, не азначае, што ваш код выконваецца ў 1 кроку, але незалежна ад таго, колькі крокаў ён, калі ён не мяняецца з памерам ўваходу, яна па-ранейшаму асімптатычна сталым, якую мы ўяўляем, як O (1). 

Як вы можаце здагадацца, Ёсць шмат розных вялікіх O вымераць час аўтаномнай працы алгарытмаў. Аб (п) ² алгарытмы асімптатычна павольней, чым O (N) алгарытмаў. Гэта значыць, як лік элементаў (N) расце, у канчатковым выніку O (п) ² алгарытмаў зойме больш часу чым O (N) алгарытмы для запуску. Гэта не азначае, O (п) алгарытмы заўсёды працаваць хутчэй чым O (N) ² алгарытмы, нават у той жа асяроддзі, на тым жа абсталяванні. Можа быць, для невялікіх памерах ўводу,  Аб (п) ² алгарытм можа на самай справе працаваць хутчэй, але, у рэшце рэшт, у якасці ўваходных памер павялічваецца да бясконцасці, Аб (п) ² алгарытму выканання у канчатковым выніку зацямніць час працы O (п) алгарытм. Як і любы квадратычнай матэматычныя функцыі  у канчатковым выніку абагнаць любой лінейнай функцыі, незалежна ад таго, колькі фору лінейная функцыя пачынаецца з. Калі вы працуеце з вялікімі аб'ёмамі дадзеных, Алгарытмы, якія працуюць у O (п) ² Час сапраўды можа ў канчатковым выніку запавольвае працу праграмы, але для невялікіх памерах ўваход, Вы, верагодна, нават не заўважаць. 

Іншы асімптатычнай складанасці, лагарыфмічнай час, O (часопіс N). Прыкладам алгарытму, які кіруе гэтым хутка гэта класічны алгарытм бінарнага пошуку, для знаходжання элемента ва ўжо адсартаваны спіс элементаў. 

Калі вы не ведаеце, што бінарны пошук робіць, Я растлумачу гэта для вас вельмі хутка. Дапушчальны, вы шукаеце нумар 3 У гэтым масіве цэлых лікаў. Ён глядзіць на сярэдзіну элемента масіва і пытаецца: "Ці з'яўляецца элемент я хачу больш, роўна або менш, чым гэта?" Калі ён роўны, то вялікі. Вы знайшлі элемент, і вы зрабілі. Калі яна больш, то вы ведаеце, элемент павінен быць у правай частцы масіва, і вы можаце толькі глядзець на гэта ў будучыні, а калі менш, то вы ведаеце, што павінна быць у левы бок. Гэты працэс паўтараецца з меншым памерам масіва пакуль правільны элемент не знойдзены. 

Гэта магутны алгарытм скарачае памер масіва ў два разы з кожнай аперацыі. Такім чынам, каб знайсці элемент у спарадкаваны масіў памерам 8, не больш (увайсці ₂ 8), ці 3 з гэтых аперацый, праверка сярэдняга элемента, то рэзка масіва ў два разы будзе неабходна, у той час як масіў памерам 16 мае (уваход ₂ 16), або 4 аперацыі. Вось толькі яшчэ 1 аперацыю для падвоіў памер масіва. Падваенне памеру масіва павялічвае час выканання толькі 1 кавалак гэтага кода. Зноў жа, праверка сярэдняга элемента спісу, то расшчапленне. Дык вось, ён сказаў, каб працаваць у лагарыфмічнай час, O (часопіс N). Але пачакайце, вы кажаце, хіба гэта не залежыць ад таго, дзе ў спісе элемент, які вы шукаеце ёсць? Што рабіць, калі першы элемент вы паглядзіце на здараецца, правільна? Тады, гэта зойме ўсяго 1 аперацыю, незалежна ад таго, наколькі вялікі спіс. 

Ну, вось чаму навукоўцы-кампутарнікі больш тэрмінаў асімптатычнай складанасці, якія адлюстроўваюць лепшым выпадку і найгоршы выступу алгарытм. Больш правільна, верхняя і ніжняя межы на час выканання. У лепшым выпадку для двайковага пошуку, наш элемент прама там, у сярэдзіне, , І вы атрымаеце яго ў пастаянны час, незалежна ад таго, наколькі вялікі астатняй частцы масіва. Сімвал, які выкарыстоўваецца для гэтага Ω. Такім чынам, гэты алгарытм называецца працаваць у Ω (1). У лепшым выпадку, яна знаходзіць элемент хутка, незалежна ад таго, наколькі вялікі масіў, а ў горшым выпадку, ён павінен выканаць (§ п) раскол праверкі масіва, каб знайсці правільны элемент. Горшы верхняй мяжы называюць з вялікай "О", што вы ўжо ведаеце. Такім чынам, гэта O (часопіс N), але Ω (1). 

Лінейны пошук, наадварот, , У якім вы ідзяце праз кожную элемент масіва , Каб знайсці той, які вы хочаце, у лепшым выпадку Ω (1). Зноў жа, першы элемент, які вы хочаце. Такім чынам, гэта не мае значэння, наколькі вялікі масіў. У горшым выпадку, гэта апошні элемент у масіве. Такім чынам, вы павінны ісці праз усе п элементаў у масіве, каб знайсці яго, Напрыклад, калі вы шукалі 3. Такім чынам, ён працуе ў O (п) таму што гэта прапарцыйна колькасці элементаў у масіве. 

Яшчэ адзін знак выкарыстоўваецца Θ. Гэта можа быць выкарыстана для апісання алгарытмаў, дзе лепшыя і горшыя выпадкі тое ж самае. Гэта датычыцца ў радок даўжынёй алгарытмаў мы гаварылі раней. Гэта значыць, калі мы захоўваем яго ў зменнай перад мы захоўваем радкі і доступ да яго пазней у пастаяннае час. Незалежна ад таго, які нумар Мы захоўванне ў гэтую зменную, мы павінны глядзець на гэта. У лепшым выпадку, мы глядзім на гэта і знайсці даўжыню радка. Так што Ω (1) ці лепшым выпадку сталай часу. У горшым выпадку, мы глядзім на яго і знайсці даўжыню радка. Такім чынам, O (1) або пастаяннай часу ў горшым выпадку. Такім чынам, паколькі ў лепшым выпадку, а горшым выпадку такія ж, гэта, можна сказаць, працуюць у Θ (1) часу. 

Такім чынам, у нас ёсць добрыя спосабы прычыне аб эфектыўнасці кодаў нічога не ведаючы пра рэальныя час яны прымаюць, каб бегчы, якая залежыць ад многіх вонкавых фактараў, у тым ліку розныя апаратныя сродкі, праграмнае забеспячэнне, ці спецыфікі вашага кода. Акрамя таго, яна дазваляе нам разважаць і пра тое, што адбудзецца , Калі памер ўваходу павялічваецца. 

Калі вы працуеце ў O (п) ² алгарытм, ці яшчэ горш, O (2 ⁿ) алгарытм, адным з найбольш хутка растучых тыпаў, Вы сапраўды пачынаеце заўважаць запаволенне калі вы пачынаеце працаваць з вялікімі аб'ёмамі дадзеных. 

Вось асімптатычнай складанасці. Дзякуй.