[Powered by Google Translate] Вероятно сте чували хората да говорят за бързо или ефективен алгоритъм
за изпълнение на конкретна задача,
но какво точно означава това за алгоритъм протече бързо и ефективно?
Е, това не говори за измерване в реално време,
като секунди или минути.
Това е така, защото компютърен хардуер
и софтуер се различават драстично.
Моята програма може да работи по-бавно от твоя,
защото аз съм я изпълняват на по-стар компютър,
или защото се случи да се играе онлайн видео игра
в същото време, което е свински паметта ми,
или може да бъде моята програма чрез различен софтуер
, която комуникира с устройството по различен начин на ниско ниво.
Това е все едно да сравняваме ябълки и портокали.
Само защото моя бавен компютър отнема повече време
от вашия да върне отговор
не означава, че имат по-ефективен алгоритъм.
>> Така че, тъй като ние не може директно да се сравнят автономна работа на програмите
в секунди или минути,
как да сравним две различни алгоритми
независимо от техния хардуер или софтуерна среда?
За да се създаде по-еднообразна начин за измерване на алгоритмични ефективност,
компютърни учени и математици са разработили
концепции за измерване на асимптотичната сложността на програмата
и нотация, наречена "Биг Ohnotation"
за описване на това.
Формалната дефиниция е, че една функция е (х)
работи по реда на грам (X)
ако съществува (х) стойност х ₀ и
някои постоянно, C, за които
е (х) е по-малка или равна на
че постоянно пъти грама (X)
за всички Х по-голямо от х ₀.
>> Но не се плаши от формалната дефиниция.
Какво означава това всъщност означава в по-теоретичен план?
Е, това е в основата на начина, по който анализира
колко бързо време на изпълнение на програмата расте асимптотично.
Това е, като размера на вашите входа се увеличава към безкрайност,
да речем, вие сте сортиране на масив с размер 1000, в сравнение с масив с размер 10.
Как растат по време на изпълнение на вашата програма?
Например, представете си брои броя на символите
в низ най-простият начин
пеша през целия низ
писмо от писмо и добавяне на 1 брояч за всеки знак.
Този алгоритъм се казва, да се движи в линейното време
по отношение на броя на символите,
"N" в низа.
С една дума, тя работи в O (N).
Защо е това?
Е, използването на този подход, времето, необходимо
да прекосяват целия низ
е пропорционален на броя на символите.
Преброяване на знаците в 20-символен низ
ще се вземат два пъти по-дълго, колкото е нужно
да разчита знаците в 10-символен низ
защото трябва да разгледаме всички герои
и всеки герой е на същия период от време да погледнете.
Както може да увеличи броя на символите,
по време на изпълнение ще се повишават линейно с дължината на входа.
>> Сега си представете, ако решите, че линейното време,
O (N), просто не е достатъчно бърз за вас?
Може би сте съхраняване на огромни струни,
и не могат да си позволят допълнително време би отнело
да преминават на героите си броим едно по едно.
Така че, можете да решите да опитате нещо различно.
Какво ще стане, ако ще се случи с вече съхранява броя на символите
в низа, да речем, в променлива наречена "дъл"
в началото на програмата,
, преди да можете дори ако тя се съхранява на първия знак в низ си?
След това всичко, което ще трябва да направя сега, за да разберете дължината на низ,
е да проверите каква е стойността на променливата е.
Може би не трябва да погледнем в себе си низ на всички,
и достъп до стойността на дадена променлива като дъл се счита за
асимптотично константно време на работа,
или O (1).
Защо е това? Е, не забравяйте, какво означава асимптотичната сложност.
Как по време на работа промяна, тъй като размерът
на вашите входове расте?
>> Да речем, че се опитвате да получите броя на знаците в по-голям низ.
Е, това не е от значение колко голям низ,
даже милион знака,
всичко, което ще трябва да направите, за да се намери дължината на низ с този подход,
е да се чете стойността на променливата дъл,
което вече.
Въвеждане на дължина, което означава, че дължината на низа, който се опитвате да намерите,
не оказва влияние върху всичко, колко бързо вашата програма работи.
Тази част от вашата програма ще тече еднакво бързо на един символен низ
и хиляди символен низ,
и затова тази програма ще бъде по-нататък за константно време
по отношение на размера на входа.
>> Разбира се, има един недостатък.
Харчат допълнително пространство в паметта на вашия компютър
съхраняване на променливата
и допълнително време, тя ще ви отведе
да направят действително съхранение на променливата,
но въпросът все още стои,
как дългия низ
не зависи от дължината на низа на всички.
Така че, тя работи в O (1) или константно време.
Това със сигурност не трябва да означава
че кодът работи в 1 стъпка,
но без значение колко стъпки е
ако тя не се променя с размера на входовете,
тя все още е асимптотично константа, която ние представляваме като O (1).
>> Както вероятно можете да се досетите,
има много различни Big O автономна работа за измерване на алгоритми с.
O (N) ² алгоритми са асимптотично по-бавно, отколкото O (N) алгоритми.
Това е, тъй като броят на елементите (н) расте,
в крайна сметка O (N) ² алгоритми ще отнеме повече време
от O (N) алгоритми да се изпълнява.
Това не означава, O (N) алгоритми винаги работи по-бързо
от O (N) ² алгоритми, дори и в една и съща среда,
на същия хардуер.
Може би за малки размери за въвеждане,
O (N) ² алгоритъм може действително да работят по-бързо,
, но в крайна сметка, като размера на входа се увеличава
към безкрайност, O (N) ² алгоритъм, по време на работа
в крайна сметка ще затъмни време на работа на алгоритъм O (N).
Просто като всяка квадратичен математическа функция
в крайна сметка ще изпревари която и да е линейна функция,
без значение колко на главата започне линейна функция започва.
Ако работите с големи обеми от данни,
алгоритми, които се движат в O (N) ² време наистина може да се окажете забавя вашата програма,
но за малки размери за въвеждане,
най-вероятно дори няма да забележите.
>> Друг асимптотичната сложност,
логаритмична време, O (дневник н).
Пример за алгоритъм, който работи бързо
е класически алгоритъм двоично търсене,
за намиране на елемент от вече сортиран списък на елементите.
>> Ако не знаете какво двоично търсене,
Ще ти обясня за вас наистина бързо.
Да речем, че търсите за номер 3
в този масив от цели числа.
Тя изглежда в средата елемент на масива
и пита: "е елемент, искам по-голямо от, равно или по-малко от това?"
Ако е еднакъв, то голяма. Намери елемент, и сте готови.
Ако е по-голям, тогава знаете елемент
трябва да бъде в дясната част на масива,
и можете да погледнете, че в бъдеще,
и ако тя е по-малък, тогава знаете, тя трябва да е в лявата страна.
Този процес се повтаря с по-малък размер масив
до правилния елемент е намерен.
>> Този мощен алгоритъм пресича размер на масива наполовина с всяка операция.
Така че, за да намерите елемент в сортиран масив с размер 8,
най-много (влезете ₂ 8),
или три от тези операции,
проверка на средата елемент, а след това рязане на масив в 1/2 ще се изисква,
като има предвид, че масив с размер 16 отнема (влезете ₂ 16),
или четири операции.
Това е само 1 операция за масив двоен размер.
Удвояването на размера на масива
увеличава по време на работа само с 1 парче на този кодекс.
Отново, проверка на средата елемент от списъка, след това разделяне.
Така че, да работят в логаритмична време,
O (Вход н).
Но чакайте, вие казвате,
не това зависи от това къде в списъка елемент, което търсите, е?
Какво става, ако първият елемент, погледнете се случва да бъде най-подходящия?
След това, тя отнема само 1 операция,
без значение колко голям е списъка.
>> Е, това е защо компютърни специалисти имат повече условия
за асимптотичната сложност, които отразяват най-добрия случай
и най-лошия случай изпълнения на алгоритъм.
По-правилно, горни и долни граници
по време на работа.
В най-добрия случай за двоично търсене, нашият елемент е
точно там в средата,
и да го получите за константно време,
без значение колко голяма е останалата част от масива.
Символът, използван за това е Ω.
Така че, този алгоритъм се казва, да се движи в Ω (1).
В най-добрия случай, той бързо намира елемент,
без значение колко голям масив,
но в най-лошия случай,
тя трябва да изпълнява (Вход н) сплит проверки
на масива, за да намерят най-подходящия елемент.
В най-лошия случай горните граници се обозначават с голямото "О", че вече знаете.
Значи, това е O (дневник н), но Ω (1).
>> Линейна търсене, от друга страна,
, в които ви преведе през всеки елемент на масива
да намерите тази, която искате,
е в най-добрия случай Ω (1).
Отново, първият елемент, който искате.
Така, че няма значение колко голям масив.
В най-лошия случай, това е последният елемент в масива.
Така че, вие трябва да преминете през всички н елементите в масива, за да го намери,
искал, ако търсите за 3.
Така че, тя работи в O (N) време
защото това е пропорционална на броя на елементите в масива.
>> Още един символ е Θ.
Това може да се използва за описание на алгоритми, където най-добрите и най-лошите случаи
са едни и същи.
Такъв е случаят в низ дължина алгоритми, за които говорихме по-рано.
Това е, ако го съхранява в променлива преди
ние съхраняваме низ и достъп до него по-късно за константно време.
Без значение какъв номер
сме съхраняване в тази променлива, ще трябва да го погледнете.
В най-добрия случай, ние гледаме на него
и да намерят дължината на низа.
Така Ω (1) или най-добрия случай константно време.
Най-лошия случай е,
ние гледаме на него и да намерят дължината на низа.
Така че, O (1) или постоянна път в най-лошия случай.
Така че, тъй като най-добрия случай и най-тежките случаи са едни и същи,
това може да се каже, да се движи в Θ (1) време.
>> В обобщение, ние имаме добри начини за причина за ефективност кодове
без да знаят нищо за реалния свят време, те да тече,
която е засегната от много външни фактори,
включително различни хардуер, софтуер,
или спецификата на кода си.
Също така, тя ни позволява да разсъждава и за това какво ще се случи
когато размерът на входа се увеличава.
>> Ако сте в O (N) ² алгоритъм,
или по-лошо, O (2 ⁿ) алгоритъм,
един от най-бързо развиващите се видове,
вие наистина ще започнете да забележите забавяне
когато започнете да работите с по-големи обеми от данни.
>> Това е асимптотичната сложност. Благодаря.