Питання Що таке звичайне англійське пояснення "Big O" позначення?


Я б вважав за краще якнайменше формальне визначення і просту математику.


4533
2018-01-28 11:10


походження


Реферат: Верхня межа складності алгоритму. Дивіться також подібне питання Великий О, як ти підраховуєш / наближаєш це? за хорошу пояснення - Kosi2801
Інші відповіді досить добре, лише одна деталь, щоб зрозуміти це: O (log n) або аналогічні засоби, що це залежить від "довжини" або "розміру" вхідного, а не від самого значення. Це може бути важко зрозуміти, але це дуже важливо. Наприклад, це трапляється, коли ваш алгоритм розбиває речі на дві в кожній ітерації. - Harald Schilly
Існує лекція, присвячена комплексності алгоритмів в лекції 8 МІТ "Вступ до комп'ютерних наук та програмування" курсу youtube.com/watch?v=ewd7Lf2dr5Q Це не зовсім простий англійський, але дає хороше пояснення з прикладами, які легко зрозуміти. - ivanjovanovic
Великий O - це оцінка найгіршої характеристики функції за умови, що алгоритм виконує максимальну кількість ітерацій. - Paul Sweatte
Big-O notation explained by a self-taught programmer - Soner Gönül


Відповіді:


Швидка примітка, це майже напевно заплутане Великі позначення O (що є верхньою межею) з позначенням Theta (що є двостороннім зв'язком). На мій досвід це насправді характерно для дискусій у неакадемічних умовах. Вибачте за будь-яку плутанину.


Велику складність O можна візуалізувати за допомогою цього графіка:

Big O Analysis

Найпростіше визначення, яке я можу дати для позначення Big-O, це:

Значення Big-O є відносним поданням складності алгоритму.

У цьому реченні є кілька важливих і свідомо вибраних слів:

  • родич: Ви можете порівняти яблука тільки з яблуками. Ви не можете порівняти алгоритм, щоб робити арифметичне множення алгоритму, який сортує список цілих чисел. Але порівняння двох алгоритмів для виконання арифметичних операцій (одне розмноження, одне додавання) скаже вам щось значуще;
  • представлення: Big-O (у його найпростішому вигляді) зменшує порівняння алгоритмів з однією змінною. Ця змінна вибирається на основі спостережень або припущень. Наприклад, алгоритми сортування, як правило, порівнюються на основі операцій порівняння (порівнюючи два вузли для визначення їх відносного упорядкування). Це припускає, що порівняння коштує дорого. Але що, якщо порівняння є дешевим, але обмін - дорого? Це змінює порівняння; і
  • складність: якщо мені потрібно зайняти одну секунду, щоб сортувати 10 000 елементів, скільки часу потрібно мені, щоб відібрати один мільйон? Складність в цьому випадку є відносною мірою до чогось іншого.

Поверніться, перечитайте вище, коли прочитали решту.

Кращий приклад Big-O, я можу придумати, це робити арифметику. Візьміть два номери (123456 і 789012). Основні арифметичні операції, які ми дізналися в школі, були:

  • доповнення;
  • віднімання;
  • множення; і
  • поділ

Кожна з них є операцією або проблемою. Спосіб їх вирішення називається а алгоритм.

Додаток є найпростішим. Ви лініруете числа вгору (праворуч) і додавайте цифри у стовпчик, в якому вказується остання кількість цього додавання в результаті. "Десятка" частини цього числа переводяться до наступного стовпця.

Припустимо, що додавання цих чисел є найдорожчою операцією в цьому алгоритмі. Слід припустити, що для того, щоб додати ці два числа разом, нам доведеться об'єднати 6 цифр (і, можливо, носіть 7). Якщо додати два цифри з 100 цифрами, ми повинні зробити 100 доповнень. Якщо додати два 10 000 цифр номера ми повинні зробити 10 000 доповнень.

Див. Малюнок? The складність (кількість операцій) прямо пропорційна кількості цифр н у більшій кількості. Ми це називаємо O (n) або лінійна складність.

Віднімання є подібним (крім вас може знадобитися позичити, а не носити).

Помноження відрізняється. Ви лініруєте цифри вгору, візьміть першу цифру в нижній номер і помножте її по черзі на кожну цифру у верхньому номері і так далі через кожну цифру. Тому для множення наших двох 6-значних чисел ми повинні зробити 36 множенням. Нам, можливо, доведеться зробити до 10 або 11 стовпців, щоб отримати кінцевий результат.

Якщо у нас є дві 100-значні цифри, ми повинні зробити 10 000 множення і 200 додавань. Для двох цифр на мільйон цифр ми повинні зробити один трильйон (1012) множення і два мільйони додає.

Оскільки алгоритм масштабується з n-квадрат, це O (n2) або квадратична складність. Це хороший час, щоб представити ще одну важливу концепцію:

Ми піклуємось тільки про найбільш значну частину складності.

Вибачте, можливо, зрозуміло, що ми можемо виразити кількість операцій: n2 + 2н. Але, як ви бачили з нашого прикладу з двома числами мільйонів цифр на одиницю, другий термін (2n) стає незначним (що становить 0,0002% від загальної кількості операцій на цьому етапі).

Можна помітити, що тут ми припустили найгірший сценарій. Під час множення 6-значних чисел, якщо один з них має 4 цифри, а інший - 6 цифр, то ми маємо лише 24 множення. Ми все-таки обчислюємо найгірший сценарій для цього "n", тобто коли обидва числа є 6-значними. Отже, запис Big-O про найгірший варіант алгоритму

Телефонна книга

Наступним кращим прикладом, який я можу думати, це телефонна книга, яка зазвичай називається Білими сторінками або подібними, але вона буде відрізнятися залежно від країни. Але я кажу про те, що список людей за прізвищем, а потім ініціали або ім'я, можливо адреса, а потім телефонні номери.

Тепер, якщо ви навчали комп'ютер шукати телефонний номер для "Джона Сміта" в телефонній книзі, яка містить 1000000 імен, що б ви зробили? Ігноруючи той факт, що можна було здогадатися, як далеко починається S (давайте припустимо, що не можемо), що б ви робили?

Типова реалізація може полягати в тому, щоб відкрити до середини, взяти 500000го і порівняйте його з "Смітом". Якщо це буває "Сміт, Джон", нам просто справді пощастило. Набагато більше імовірно, що "Джон Сміт" буде до або після цього імені. Якщо це буде після того, як ми потім розділимо останню половину телефонної книги наполовину і повторіть. Якщо це до цього, ми розділимо першу половину телефонної книги наполовину і повторіть. І так далі.

Це називається а бінарний пошук і використовується щодня в програмуванні, розумієш чи ні.

Тому, якщо ви хочете знайти ім'я в телефонній книзі з мільйонами імен, ви можете знайти ім'я, зробивши це максимально 20 разів. При порівнянні алгоритмів пошуку ми вирішили, що це порівняння є нашим 'n'.

  • Для телефонної книги з 3 іменами потрібно 2 порівняння (максимум).
  • За 7 вона займає не більше 3.
  • За 15 років це займає 4.
  • ...
  • Для 1 000 000 потрібно 20.

Це неймовірно добре, чи не так?

У умовах Big-O це так O (log n) або логарифмічна складність. Зараз відповідний логарифм може бути ln (base e), log10, журнал2 або інша база. Неважливо, що це все ще O (log n), як і O (2n2) і O (100н2) як і раніше, і О (n2)

Тут варто пояснити, що Big O може бути використаний для визначення трьох випадків з алгоритмом:

  • Кращий випадок: У телефонній книзі пошук найкраще - ми знайдемо ім'я в одному порівнянні. Це O (1) або постійна складність;
  • Очікуваний випадок: Як обговорювалося вище, це O (log n); і
  • Найгірший випадок: Це також O (log n).

Зазвичай ми не дбаємо про найкращий випадок. Ми зацікавлені в очікуваному і найгіршому випадку. Іноді один чи інший з них буде більш важливим.

Повернутися до телефонної книги.

Що робити, якщо у вас є номер телефону і ви хочете знайти ім'я? Поліція має зворотну телефонну книгу, але такі розшуки заперечуються широкій публіці. Або вони? Технічно ви можете повернути пошук номера в звичайній телефонній книзі. Як?

Ви починаєте з імені і порівнюєте номер. Якщо це матч, чудово, якщо ні, то переходите до наступного. Ви повинні зробити це таким чином, оскільки є телефонна книга невпорядкований (за номером телефону в будь-якому випадку).

Тому, щоб знайти назву з номером телефону (зворотний пошук):

  • Кращий випадок: O (1);
  • Очікуваний випадок: O (n) (для 500 000); і
  • Найгірший випадок: O (n) (для 1 000 000).

Подорожуючий торговець

Це досить відома проблема в галузі комп'ютерних наук і заслуговує на увагу. У цій проблемі у вас є N міст. Кожне з цих міст пов'язане з одним або кількома іншими містами дорогою певної відстані. Проблема "Подорожуючий продавець" - знайти найкоротший тур, який відвідує кожне місто.

Звучить просто? Подумати ще раз.

Якщо у вас є 3 міста А, В та С з дорогами між усіма парами, то ви можете піти:

  • A → B → C
  • A → C → B
  • B → C → A
  • B → A → C
  • C → A → B
  • C → B → A

Ну, насправді це менше, тому що деякі з них еквівалентні (A → B → C і C → B → A еквівалентні, наприклад, тому що вони використовують ті ж дороги, тільки в зворотному порядку).

Насправді є 3 можливості.

  • Візьміть це до 4 міст, і у вас є (iirc) 12 можливостей.
  • З 5 це 60.
  • 6 стає 360.

Це функція математичної операції під назвою a Факторіал. В основному:

  • 5! = 5 × 4 × 3 × 2 × 1 = 120
  • 6! = 6 × 5 × 4 × 3 × 2 × 1 = 720
  • 7! = 7 × 6 × 5 × 4 × 3 × 2 × 1 = 5040
  • ...
  • 25! = 25 × 24 × ... × 2 × 1 = 15,511,210,043,330,985,984,000,000
  • ...
  • 50! = 50 × 49 × ... × 2 × 1 = 3.04140932 × 1064

Отже, Big-O проблеми з подорожуючим продавцем O (n!) або факторіальна або комбінаторна складність.

До того часу, коли ви отримаєте 200 міст, у Всесвіті не вистачає часу для вирішення проблеми з традиційними комп'ютерами.

Щось подумати.

Поліноміальний час

Інший момент, я хотів би швидко згадати про те, що будь-який алгоритм, який має складність O (na) як кажуть, є поліноміальна складність або вирішується в поліноміальний час.

O (n), O (n2) і т. д. - все поліноміальне час. Деякі проблеми не можуть бути вирішені в поліномиальному часі. У зв'язку з цим в світі використовуються певні речі. Криптографія відкритого ключа є найважливішим прикладом. Обчислювально складно знайти два прості чинники дуже великого числа. Якщо цього не було, ми не змогли використати системи відкритого ключа, які ми використовуємо.

У всякому разі, саме це стосується мого (сподіваюся, звичайного англійського) пояснення Big O (переглянуте).


6094
2018-01-28 11:18



Хоча інші відповіді зосереджуються на поясненні відмінностей між O (1), O (n ^ 2) та ін .... ваша точка, яка деталізує, як алгоритми можуть бути класифіковані в n ^ 2, nlog (n) та ін + 1 за хорошу відповідь, що допомогло мені зрозуміти запис Big O також - Yew Long
Можна додати, що big-O представляє верхню межу (задану алгоритмом), big-Omega дає нижню межу (зазвичай дається як доказ, незалежний від певного алгоритму), а big-Theta означає, що "оптимальний" алгоритм досягнення цієї нижньої межі. - mdm
Це добре, якщо ви шукаєте найдовшу відповідь, але не для відповіді, яка найкращим чином пояснює Big-O просто. - kirk.burleson
-1: Це абсолютно неправильно: _ "BigOh - відносне представлення складності алгоритму". № BigOh є асимптотичною вершиною і існує досить добре, незалежно від комп'ютерної науки. O (n) лінійний. Ні, ви збентежите BigOh з тетою. log n - це O (n). 1 є O (n). Кількість зворотних коментарів до цієї відповіді (і коментарів), що робить основну помилку, що збиває з собою Тету з BigOh, є досить сумнівною ...
"До того часу, коли ви отримаєте 200 міст, у Всесвіті не вистачає часу для вирішення проблеми з традиційними комп'ютерами". Коли Всесвіт закінчується? - Isaac


Це показує, як алгоритм масштабується.

O (n2): відомий як Квадратична складність

  • 1 товар: 1 секунда
  • 10 елементів: 100 секунд
  • 100 елементів: 10000 секунд

Зверніть увагу, що кількість предметів збільшується в 10 разів, але час збільшується в 10 разів2. В основному, n = 10 і так O (n2) дає нам коефіцієнт масштабування n2 який становить 102.

O (n): відомий як Лінійна складність

  • 1 товар: 1 секунда
  • 10 предметів: 10 секунд
  • 100 елементів: 100 секунд

На цей раз кількість предметів збільшується в 10 разів, а також час. n = 10, і тому масштабний коефіцієнт O (n) - 10.

O (1): відомий як Постійна складність

  • 1 товар: 1 секунда
  • 10 пунктів: 1 секунда
  • 100 елементів: 1 секунда

Кількість предметів все ще збільшується в 10 разів, але масштабний коефіцієнт O (1) завжди становить 1.

O (log n): відомий як Логарифмічна складність

  • 1 товар: 1 секунда
  • 10 пунктів: 2 секунди
  • 100 предметів: 3 секунди
  • 1000 предметів: 4 секунди
  • 10000 елементів: 5 секунд

Кількість обчислень збільшується лише за допомогою журналу вхідного значення. Отже, в цьому випадку, припускаючи, що кожне обчислення займає 1 секунду, журнал вводу n це час, необхідний, отже log n.

Це суть цього. Вони зменшують математику, тому це може бути не точно n2 або все, що вони кажуть, але це буде домінуючим фактором масштабування.


662
2018-01-28 11:28



що саме означає це визначення? (Кількість предметів все більше збільшується в 10 разів, але масштабний коефіцієнт O (1) завжди становить 1.) - HollerTrain
Не секунд, операцій. Також ви пропустили факторіально-логарифмічний час. - Chris Charabaruk
Це не дуже добре пояснює, що O (n ^ 2) може описувати алгоритм, який працює точно .01 * n ^ 2 + 999999 * n + 999999. Важливо знати, що алгоритми порівнюються за допомогою цієї шкали, і що порівняння працює, коли n є "досить великим". Timsort Python насправді використовує сортування вставки (найгірший / середній випадок O (n ^ 2)) для малих масивів через те, що він має невеликі накладні витрати. - Darthfett
Ця відповідь також плутає велику нотацію O та позначення Тети. Функція n, яка повертає 1 для всіх його входів (як правило, просто записується як 1), насправді знаходиться в O (n ^ 2) (хоча це також і в O (1)). Аналогічним чином алгоритм, який повинен виконувати лише один крок, який займає постійну кількість часу, також вважається алгоритмом O (1), але також є алгоритмом O (n) і O (n ^ 2). Але, можливо, математики та комп'ютерні вчені не погоджуються з визначенням: - /. - Jacob Akkerboom
Логарифмічна складність O (log n), що розглядається в даному відповіді, є базою 10. Як правило, стандарт слід обчислити з базою 2. Слід пам'ятати про цей факт і не слід плутати. Також, як згадував @ ChrisCharabarur, складність позначає кількість операцій, а не секунд. - Aksh1801


Значення Big-O (також називається позначенням "асимптотичного зростання") є які функції "виглядають", коли ви ігноруєте постійні фактори та речі поблизу джерела. Ми використовуємо його для обговорення як справи масштабні.


Основи

для "досить" великих входів ...

  • f(x) ∈ O(upperbound) засоби f "зростає не швидше, ніж" upperbound
  • f(x) ∈ Ɵ(justlikethis) означає f "росте точно як" justlikethis
  • f(x) ∈ Ω(lowerbound) засоби f "росте не повільніше, ніж" lowerbound

Великі позначення O не піклуються про постійні фактори: функції 9x² як кажуть, "росте точно, як" 10x². Також не великий - О асимптотичний нотації догляду неасимптотичний речі ("речі поблизу джерела" або "що трапляється, коли розмір заданої величини невеликий"): функція 10x² як кажуть, "росте точно, як" 10x² - x + 2.

Чому б ви не хотіли ігнорувати менші частини рівняння? Тому що вони стають цілком занедбаними великими частинами рівняння, оскільки ви розглядаєте більші та більші шкали; їх внесок стає карликовим і не має значення. (Див. Розділ прикладу.)

Поставте інший спосіб, це все про співвідношення як ви йдете до нескінченності. Якщо ви ділите фактичний час, який він потребує O(...), ви отримаєте постійний фактор у межах великих витрат. Інтуїтивно це має сенс: функції "масштабують" один одного, якщо ви можете помножити його, щоб отримати інший. Тобто, коли ми говоримо ...

actualAlgorithmTime(N) ∈ O(bound(N))
                                       e.g. "time to mergesort N elements 
                                             is O(N log(N))"

... це означає що для "досить великих" розмірів задачі N (якщо ми ігноруємо речі поблизу джерела) існує певна константа (наприклад, 2.5, повністю зроблена) така, що:

actualAlgorithmTime(N)                 e.g. "mergesort_duration(N)       "
────────────────────── < constant            ───────────────────── < 2.5 
       bound(N)                                    N log(N)         

Є багато варіантів постійного; часто "найкращий" вибір відомий як "постійний фактор" алгоритму ... але ми часто ігноруємо це, як ми ігноруємо не найбільші терміни (див. розділ Постійні фактори, чому вони, як правило, не мають значення). Ви також можете подумати про вищезгадане рівняння як обмежене, кажучи "У гіршому випадку час, який він потребує, ніколи не буде гіршим, ніж грубо N*log(N), у межах 2.5 (постійний фактор, про який ми не дбаємо)".

В загальному, O(...) є найбільш корисним, тому що ми часто дбаємо про найгірші випадки поведінки. Якщо f(x) представляє щось "погане", як процесор або пам'ять, то "f(x) ∈ O(upperbound)" засоби "upperbound є найгіршим сценарієм використання процесора / пам'яті ".


Програми

Будучи чисто математичною конструкцією, записування big-O не обмежується лише розмовами про обробку часу та пам'яті. Ви можете використовувати це, щоб обговорити асимптотику будь-якого значення масштабування, наприклад:

  • кількість можливих рукостискань серед N люди на вечірці (Ɵ(N²), зокрема N(N-1)/2, але що важливо, це "вага, як" )
  • імовірнісна очікувана кількість людей, які бачили певний вірусний маркетинг як функцію часу
  • як затримується веб-сайт із кількістю оброблюваних пристроїв у процесорі або графічному процесорі чи комп'ютерному кластері
  • як зменшується теплова потужність на ЦП, як функція підрахунку транзистора, напруги тощо.
  • скільки часу потрібно запустити, як функція розміру вводу
  • скільки місця для запуску алгоритму, як функцію від розміру входу

Приклад

Для прикладу рукостискання вище кожен у кімнаті трясе всіма руками. У цьому прикладі #handshakes ∈ Ɵ(N²). Чому?

Трохи коректно: кількість рукостискань точно n-select-2 або N*(N-1)/2 (кожен з N людей потискає руки інших людей N-1, але це подвійне кількість рукостискань поділяють на 2):

everyone handshakes everyone else. Image credit and license per wikipedia/wikimedia commons "complete graph" article.  adjacency matrix

Проте для дуже великої кількості людей лінійний термін N є карликовим і ефективно вносить 0 до співвідношення (на графіку: частка порожніх ящиків по діагоналі над загальними коробками зменшується, коли кількість учасників збільшується). Тому масштабова поведінка є order N², або кількість рукостискань "зростає, як N²".

#handshakes(N)
────────────── ≈ 1/2
     N²

Це як би не було там навіть порожніх ящиків на діагоналі таблиці (N * (N-1) / 2 checkmarks) (N2 асимптотичні позначки).

(тимчасовий відступ від "звичайного англійського" :) Якщо ви хочете довести це собі, ви можете виконати деяку просту алгебра на співвідношенні, щоб розділити її на кілька умов (limозначає "розглянутий в межах", просто ігноруйте його, якщо ви цього не бачили, це просто позначення для "і N дійсно дуже великий"):

    N²/2 - N/2         (N²)/2   N/2         1/2
lim ────────── = lim ( ────── - ─── ) = lim ─── = 1/2
N→∞     N²       N→∞     N²     N²      N→∞  1
                               ┕━━━┙
             this is 0 in the limit of N→∞:
             graph it, or plug in a really large number for N

tl; dr: Кількість рукостискань "виглядає як" x² стільки для великих значень, що якщо б ми хотіли записати співвідношення # handshakes / x², той факт, що нам це не потрібно точно Рукостискання x² навіть не відображатиметься в десятковому значенні за довільно великий час.

наприклад, для x = 1 мільйон, коефіцієнт # рукостискань / x²: 0.499999 ...


Будівельна інтуїція

Це дозволяє нам робити заяви як ...

"Для достатньо великих значень inputsize = N, незалежно від того, який постійний чинник, якщо я подвійний розмір входу


362
2017-07-08 04:46



Відмінна математична відповідь, але О.П. попросив просте англійська відповідь. Цей рівень математичного опису не потрібно для розуміння відповіді, хоча для людей, особливо математично налаштованих, це може бути набагато простішим для розуміння, ніж "звичайний англійський". Однак О.П. попросив останнього. - El Zorko
Можливо, люди, крім ОП, можуть зацікавитись відповідями на це питання. Хіба це не керівний принцип сайту? - Casey
Хоча я можу, мабуть, зрозуміти, чому люди можуть зняти мою відповідь і думати, що це занадто математично (особливо "математика - це новий звичайний англійський"), оригінальне запитання про великі, що стосуються функцій, тому я спробуй бути явним і говорити про функції таким чином, що доповнює простий англійської інтуїції. Мова тут часто може бути глянсована або зрозуміла з фоном математики високого класу. Я відчуваю, що люди можуть дивитися на Math Addenda в кінці, хоча, і припустити, що це частина відповіді, коли він просто там, щоб побачити, що реальний математика виглядає. - ninjagecko
Це фантастична відповідь; набагато краще ІМО, ніж той, хто має найбільше голосів. Необхідна "математика" не виходить за межі того, що потрібно для розуміння виразів у дужках після "O", яке не може обійтися без розумного пояснення, яке використовує будь-які приклади. - Dave Abrahams
"f (x) ∈ O (верхня межа) означає, що f" зростає не швидше, ніж "upperbound", ці три просто сформульовані, але математично правильні пояснення великих Oh, Theta та Omega є золотими. Він описав для мене на англійській мові той факт, що 5 різних джерел, здавалося, не перекладали на мене без написання складних математичних виразів. Спасибі людині! :) - timbram


EDIT: Швидка примітка, це майже напевно заплутане Великі позначення O (що є верхньою межею) з позначенням Theta (що є як верхньою, так і нижньою межею). На мій досвід це насправді характерно для дискусій у неакадемічних умовах. Вибачте за будь-яку плутанину.

У одному реченні: як збільшується ваша робота, скільки часу потрібно для його завершення?

Очевидно, що це тільки використання "розміру" як вхідного і "часу зайнято" як вихідний - та сама ідея застосовується, якщо ви хочете поговорити про використання пам'яті тощо.

Ось приклад, де ми маємо N футболки, які ми хочемо висохнути. Добре припустити це неймовірно швидко, щоб отримати їх у позицію сушіння (тобто взаємодія людини незначна). Звичайно, це не справа в реальному житті ...

  • Використовуючи лінію для прання назовні: якщо ви маєте нескінченно великий задній двір, прання висихає через O (1) час. Тим не менш, у вас є це, він отримає той же сонце і свіже повітря, тому розмір не впливає на час сушіння.

  • Використання сушарки для ванної кімнати: ви вкладете 10 рукавичок у кожне навантаження, а потім вони закінчені через годину. (Ігнорувати фактичні числа тут - вони не мають значення.) Таким чином, сушіння займає 50 сорочок про 5 разів довше, ніж сушіння 10 сорочок.

  • Вклавши все в провітрювальний шафа: якщо ми поставимо все в одну велику купу і просто дамо загальне тепло, це займе багато часу, щоб середні сорочки висихали. Я б не хотів догадуватися про деталі, але я підозрюю, що це, принаймні, O (N ^ 2), - коли ви збільшуєте навантаження, час висихання збільшується швидше.

Одним з важливих аспектів позначення "великого O" є те, що він не робить скажіть який алгоритм буде швидшим для заданого розміру. Візьміть хеш-таблицю (рядок-ключ, ціле значення) проти масиву пар (рядок, ціле число). Чи швидше знайти ключ у хешбалі або елементі масиву, заснований на рядку? (тобто для масиву "знайдіть перший елемент, де частина рядка відповідає даній клавіші"). Швидкі шаблони, як правило, амортизуються (~ = "в середньому") O (1) - після їх налаштування, воно повинно займати близько той самий час, щоб знайти запис у 100 таблицях записів, як у таблиці з 1 000 000 записів. Знаходження елемента в масиві (на основі вмісту, а не індексу) є лінійним, тобто O (N) - в середньому, вам доведеться шукати половину записів.

Це робить хешбет швидким, ніж масив для пошуку? Не обов'язково. Якщо у вас є дуже мала колекція записів, масив може бути швидшим - ви можете перевірити всі рядки у потрібний час, щоб просто обчислити хеш-код того, що ви дивитесь. Як тільки набір даних зростає, проте, хеш-таблиця в кінцевому рахунку переможе масив.


237
2018-01-28 11:16



Для хешування вимагається алгоритм запуску для розрахунку індексу фактичного масиву (залежно від реалізації). А масив просто має O (1), тому що це просто адреса. Але це не має нічого спільного з питанням, просто спостереженням :) - Filip Ekberg
пояснення Джона має дуже важливе значення для питання, яке я думаю. це точно, як можна було б пояснити це матір'ю, і вона зрештою зрозуміє це, я думаю :) мені подобається приклад одягу (зокрема, останній, де пояснюється експоненціальне зростання складності) - Johannes Schaub - litb
Філіпп: Я не кажу про адресу масиву по індексу, я маю на увазі пошук відповідного запису в масиві. Не могли б ви перечитати відповідь і подивитися, чи це все ще незрозуміло? - Jon Skeet
@Filip Ekberg Я думаю, що ви думаєте про таблицю прямих адрес, де кожен індекс карту до ключа безпосередньо, отже, є O (1), однак я вважаю, що Джон розмовляє про несортований масив ключових / val пар, які потрібно шукати через лінійно. - ljs
@ RBT: Ні, це не подвійний пошук. Це може дійти до правильного хешу відро відразу, просто на основі перетворення з хеш-коду в індекс ведра. Після цього, пошук потрібного хеш-коду в ковші може бути лінійним або він може бути бінарним пошуком ... але до того часу ви досягли дуже невеликої частки загального розміру словника. - Jon Skeet


Великий O описує верхню межу для поведінки зростання функції, наприклад, час виконання програми, коли входи стають великими.

Приклади:

  • O (n): якщо я подвоїв розмір вводу, то runtime подвоюється

  • O (n2): Якщо розмір входу подвоює чотири рази часу виконання

  • O (log n): якщо розмір входу вдвічі збільшує час виконання на один

  • O (2н): Якщо розмір входу збільшується на один, час виконання подвоюється

Розмір входу зазвичай є пробілом у бітах, необхідних для подання вхідного сигналу.


120
2018-01-28 11:23



неправильно! наприклад O (n): якщо я подвоїв розмір входу, час виконання буде множитися на кінцеву не нульову константу. Я маю на увазі O (n) = O (n + n) - arena-ru
Я говорю про f в f (n) = O (g (n)), а не g, як ви, здається, розумієте. - starblue
Я подумав, але останнє речення не робить багато чого, я відчуваю. Ми часто не говоримо про "біти" при обговоренні чи вимірюванні Big (O). - cdiggins
Ви повинні додати приклад для O (n log n). - Christoffer Hammarström
Це не так вже й зрозуміло, по суті він поводить себе трохи гірше, ніж O (n). Отже, якщо n подвоюється, то час виконання множиться на коефіцієнт, дещо більший за 2. - starblue


Великі нотатки O найчастіше використовуються програмістами як приблизний показник, скільки часу потрібно виконати обчислення (алгоритм), виражене як функція розміру набору входів.

Великий O є корисним для порівняння того, наскільки добре зросте два алгоритми, коли збільшується кількість введених даних.

Точніше Великі позначення O використовується для вираження асимптотичної поведінки функції. Це означає, як функція поводиться, коли вона наближається до нескінченності.

У багатьох випадках "O" алгоритму потрапить в одне з таких випадків:

  • O (1) - Час завершення однаковий, незалежно від розміру вхідного набору. Прикладом є доступ до елементу масиву за індексом.
  • O (Log N) - Час завершення збільшення приблизно відповідає log2 (n). Наприклад, 1024 елементи займає приблизно вдвічі більше, ніж 32 одиниці, тому що Log2 (1024) = 10 і Log2 (32) = 5. Прикладом є пошук елемента в двійкове дерево пошуку (BST).
  • O (N) - Час, щоб завершити цю шкалу лінійно з розміром набору введення. Іншими словами, якщо ви подвоїте кількість елементів у наборі введення, алгоритм займає приблизно в два рази довший. Прикладом є підрахунок кількості елементів у пов'язаному списку.
  • O (N Log N) - Час завершення збільшення на кількість одиниць, що перевищують результат Log2 (N). Прикладом цього є купу сортувати і швидко сортувати.
  • O (N ^ 2) - Час завершення приблизно дорівнює квадрату кількості предметів. Прикладом цього є міхур сортувати.
  • O (N!) - Час завершення - це факториал набору вхідних даних. Прикладом цього є Подорожній продавцеві проблема грубої сили рішення.

Великі O ігнорують фактори, які не впливають на зміст кривої зростання функції, оскільки розмір вхідних значень збільшується до нескінченності. Це означає, що константи, які додаються або помножуються на функцію, просто ігноруються.


97
2017-09-05 16:31



cdiggins, що, якби я мав O (N / 2) складність, повинен бути O (N) або O (N / 2), наприклад, яка складність, якщо я буду петля над половиною рядка. - Melad Ezzat
@Melad Це приклад константи (0.5), множиться на функцію. Це ігнорується, оскільки вважається, що він має суттєвий ефект для дуже великих значень N. - cdiggins


Великий O - це лише спосіб "Експресувати" себе спільним способом: "Скільки часу / простору потрібно для запуску мого коду?".

Ви часто можете побачити O (n), O (n2), O (nlogn) і так далі, всі ці просто способи показати; Як змінюється алгоритм?

O (n) означає, що Big O є n, і тепер ви можете подумати: "Що таке n !?" Добре "n" - це кількість елементів. Imaging ви хочете шукати елемент у масиві. Вам доведеться шукати кожен елемент і як "Ви правильний елемент / елемент?" у гіршому випадку цей елемент знаходиться на останньому індексі, а це означає, що це займає стільки ж часу, скільки є елементів у списку, тому ми маємо назву "ой, хай, це справедлива дана кількість значень!" .

Отже, ви можете зрозуміти, що "російська"2"означає, але, щоб бути ще більш конкретним, грати з думкою, що у вас є простий, найпростіший з алгоритмів сортування; bubblesort. Цей алгоритм повинен переглядати весь список для кожного елемента.

Мій список

  1. 1
  2. 6
  3. 3

Потік тут буде:

  • Порівняйте 1 і 6, що є найбільшим? Ok 6 знаходиться у правильному положенні, рухаючись вперед!
  • Порівняйте 6 і 3, о, 3 менше! Давайте перейдемо, о, список змінився, ми повинні почати з самого початку!

Це О n2 тому що, ви повинні подивитися на всі елементи у списку, є "n" елементи. Для кожного елемента ви переглядаєте всі елементи ще раз, для порівняння це також "n", тому для кожного елемента ви виглядаєте "n" разів, що означає n * n = n2

Я сподіваюся, що це так просто, як ви цього хочете.

Але пам'ятайте, що Великий О - це лише спосіб, що дозволяє розібратися у способі часу та простору.


77
2018-01-28 11:14



для logN ми вважаємо, що для циклу, що працює від 0 до N / 2, як щодо O (log log N)? Я маю на увазі, як виглядає програма? пробач мені за чисті навички математики - Pablo Escobar


Великий O описує основний масштабний характер алгоритму.

Є багато інформації, що Big O не розповідає вам про даному алгоритмі. Він скорочує кістку і дає лише інформацію про масштабність алгоритму, зокрема, про те, як ресурс (думаю про час або пам'ять) масштабу алгоритму у відповідь на "розмір входу".

Розглянемо різницю між паровою машиною і ракетою. Вони не просто різноманітні ті самі речі (як, скажімо, двигун Prius проти двигуна Lamborghini), але вони суттєво відрізняються різними типами двигунів. Парова машина може бути швидшою, ніж іграшкова ракета, але паровий поршневий двигун не зможе досягти швидкості орбітальної ракети-носія. Це відбувається тому, що ці системи мають різні масштабовані характеристики відносно необхідного палива ("використання ресурсу") для досягнення заданої швидкості ("розмір вхідного сигналу").

Чому це так важливо? Оскільки програмне забезпечення вирішує проблеми, які можуть відрізнятися за розміром факторами до трильйону. Розглянемо це на мить. Співвідношення між швидкістю, необхідною для подорожі до Місяця та швидкості руху людини, становить менше 10 000: 1, і це абсолютно крихітне порівняно з діапазоном програмного забезпечення розмірів вхідних даних. І тому, що програмне забезпечення може зіткнутися з астрономічним діапазоном у розмірах вхідних даних, існує потенціал для складності Великого алгоритму, це принцип масштабування, щоб супроводжувати будь-які деталі виконання.

Розглянемо канонічний приклад сортування. Пузир-сортування - це O (n2), а merge-sort - O (n log n). Скажімо, у вас є дві програми для сортування: програма A, яка використовує сортування типу bubble-sort та додаток B, який використовує зразок злиття, і припустимо, що для розмірів вхідних даних близько 30 елементів програма A на 1000x швидше, ніж прикладна програма B при сортуванні. Якщо вам ніколи не потрібно сортувати набагато більше, ніж 30 елементів, то очевидно, що вам слід віддавати перевагу застосунку А, оскільки це набагато швидше на цих розмірах. Однак, якщо ви виявите, що вам, можливо, доведеться сортувати десять мільйонів елементів, то, що ви очікуєте, це те, що програма B дійсно закінчується у тисячі разів швидше, ніж додаток A, у цьому випадку, цілком залежно від того, як кожен алгоритм масштабує.


52
2018-01-28 13:12