[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 ⁿ) алгоритм, одним з найбільш швидко зростаючих типів, Ви дійсно починаєте помічати сповільнення коли ви починаєте працювати з великими обсягами даних. 

Ось асимптотичної складності. Спасибі.