Питання Що точно означає O (log n)?


Я в даний час дізнаюся про Big O Notation часів роботи та амортизованих разів. Я розумію поняття O (n) лінійний час, що означає, що розмір входу впливає на зростання алгоритму пропорційно ... і те ж саме стосується, наприклад, квадратного часу O (n2) і т. д. навіть алгоритми, такі як генератори перестановки, з O (n!) рази, які ростуть за факторами.

Наприклад, така функція є O (n) тому що алгоритм зростає пропорційно його вводу н:

f(int n) {
  int i;
  for (i = 0; i < n; ++i)
    printf("%d", i);
}

Точно так само, якщо була вкладена петля, то час буде O (n2)

Але що це таке? O (log n)? Наприклад, що означає сказати, що висота повного двійкового дерева O (log n)?

Я знаю (може бути, не дуже докладно), який логарифм, в тому сенсі, що: log10 100 = 2, але я не можу зрозуміти, як визначити функцію з логарифмічним часом.


1736
2018-02-21 20:05


походження


Двійкове дерево 1-вузла має висоту log2 (1) +1 = 1, дерево 2-вузла має висоту log2 (2) +1 = 2, дерево 4-вузла має висоту log2 (4) +1 = 3 і так далі Дерево n-вузла має висоту log2 (n) +1, тому додавання вузлів до дерева змушує його середній висоту логарифмічно зростати. - David R Tribble
Одне, що я бачу в більшості відповідей, це те, що вони по суті описують "O (щось)", означає, що час роботи алгоритму зростає пропорційно "щось". Враховуючи, що ви попросили "точне значення" в "O (log n)", це не так. Це інтуїтивно зрозумілий опис значень Big-Theta, а не Big-O. O (log n) інтуїтивно означає, що час роботи зростає не більше пропорційно "log n": stackoverflow.com/questions/471199/... - Mehrdad Afshari
Я завжди пам'ятаю розбити і перемогти як приклад для O (log n) - RichardOD
Важливо усвідомлювати, що його база журналу 2 (не база 10). Це тому, що на кожному кроці алгоритму ви видалите половину залишкового вибору. У комп'ютерній науці ми майже завжди маємо справу з журналом 2, тому що ми можемо ігнорувати константи. Однак існують деякі винятки (наприклад, тривалість виконання Quad Tree - це база журналу 4) - Ethan
@ Етан: Неважливо, в якій базі ви знаходитесь, оскільки базова конверсія - це лише постійне множення, Формула - log_b (x) = log_d (x) / log_d (b). Log_d (b) просто буде константою. - mindvirus


Відповіді:


Я не можу зрозуміти, як визначити функцію з часом журналу.

Найбільш поширеними атрибутами логарифмічної функції часу є те, що:

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

або

  • елементи, на яких виконується дія, - цифри n

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

Звичайно, більша телефонна книга все одно займе більше часу, але вона не буде зростати так швидко, як пропорційне збільшення додаткового розміру.


Ми можемо розгорнути приклад телефонної книги, щоб порівняти інші види операцій та їх тривалість роботи. Ми припустимо, що в нашій телефонній книзі є підприємства ("Жовті сторінки"), які мають унікальні назви та Люди ("Білі сторінки"), які можуть не мати унікальних імен. Номер телефону призначається не більше однієї людини або бізнесу. Ми також вважатимемо, що для переходу на певну сторінку потрібен постійний час.

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

  • O (1) (кращий випадок): Якщо ввести назву компанії та назву компанії, знайдіть номер телефону.

  • O (1) (середній випадок): Вказуючи номер сторінки, в якій вказано ім'я особи та його ім'я, знайдіть номер телефону.

  • O (log n): Вказуючи ім'я людини, знайдіть номер телефону, вибравши випадкову точку приблизно на півдорозі через частину книги, яку ви ще не шукали, а потім перевірити, чи є ім'я особи в той момент. Потім повторіть процес на півдорозі через частину книги, в якій лежить ім'я людини. (Це бінарний пошук для імені людини.)

  • O (n): Знайдіть всіх людей, чиї номери телефонів містять цифру "5".

  • O (n): Вказуючи номер телефону, знайдіть людину чи компанію з цим номером.

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

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

  • O (n log n): Ми хочемо персоналізувати телефонну книгу, тому ми збираємося знайти кожну особу чи назву компанії в зазначеній копії, потім назвіть їх ім'я в книзі та напишіть коротку подяку за їх патронаж.

  • O (n2): Помилка відбулася в офісі, і кожен запис у кожній телефонній книзі має додатковий «0» в кінці номера телефону. Візьміть деяку білизну та видаліть кожен нуль.

  • O (n · n!): Ми готові завантажити телефонні книги на док-станцію доставки. На жаль, робот, який мав завантажувати книги, потрапив у хайвір: він виставляє книги на вантажівку у випадковому порядку! Ще гірше, він завантажує всі книги на вантажівку, а потім перевіряє, чи вони в правильному порядку, і якщо ні, то вони завантажують їх і починаються згори. (Це страшне бого роду.)

  • O (nн): Ви виправляєте робота так, щоб він завантажував речі правильно. На наступний день один з ваших співробітників сплесне на вас і потягне завантажувальний робот до автоматизованих систем друку. Кожен раз, коли робот завантажує оригінальну книгу, фабричний принтер робить копію всіх телефонних книжок! На щастя, системи виявлення помилок робота досить складні, тому що робот не намагається друкувати ще більше копій, коли він стикається з дублікатом книги для завантаження, але він все ще повинен завантажити кожну оригінальну та дубльовану книгу, яка була надрукована.


2182
2018-02-21 20:14



@cletus: Поза сумнівом, я боюсь. Я підібрав це тому, що телефонні книги мають великий N, люди розуміють, що вони є та що вони роблять, і тому, що це універсальний приклад. Плюс я повинен користуватися роботами в моєму поясненні! Перемога навколо. (Крім того, схоже, що ваша відповідь була зроблена, перш ніж я навіть був учасником StackOverflow, щоб почати!) - John Feminella
"Помилка відбулася в офісі, і кожен запис у кожній телефонній книзі має додатковий символ" 0 "в кінці номера телефону. Зробіть деякий вибій та видаліть кожен нуль". <- це не замовлення N квадрата. N визначається як розмір входу. Розмір вводу - це кількість телефонних номерів, тобто число чисел за книгу, що дорівнює кількості книг. Це все одно лінійна операція часу. - Billy ONeal
@Billy: У цьому прикладі N це кількість людей в одній книзі. Оскільки кожна людина в телефонній книзі також отримує власну копію книги, є N  однаковий телефонні книги, кожен з N люди в ньому, що є O (N ^ 2). - John Feminella
Чи не O (1) найкращий випадок, а не гірший випадок, як це дивно виділено як? - Svip
Мені знадобилося час O (long⅝n! N-55/2), щоб знайти визначення O (log n), яке, нарешті, має сенс. +1 - iAteABug_And_iLiked_it


На це питання вже розміщено багато хороших відповідей, але я вважаю, що ми дійсно не маємо важливого - це ілюстрована відповідь.

Що означає сказати, що висота повного двійкового дерева - O (log n)?

Наступний малюнок зображує бінарне дерево. Зверніть увагу, як кожен рівень містить подвійну кількість вузлів у порівнянні з рівнем вище (отже бінарний):

Binary tree

Двійковий пошук є прикладом зі складністю O(log n). Скажімо, вузли в нижньому рівні дерева на малюнку 1 представляють елементи в деякій сортованій колекції. Двійковий пошук - це алгоритм розбиття і перемотування, а малюнок показує, як нам потрібно (максимум) 4 порівняння, щоб знайти запис, який ми шукаємо в цьому наборі даних з 16 елементів.

Припустимо, ми мали натомість набір даних із 32 елементами. Продовжуйте малюнок вище, щоб дізнатись, що зараз нам потрібно 5 порівнянь, щоб знайти те, що ми шукаємо, оскільки дерево виросло на одному рівні глибше, коли ми помножили обсяг даних. У результаті складність алгоритму може бути описана як логарифмічний порядок.

Малювання log(n) на рівній папірі, приведе до графіка, де підйом кривої сповільнюється як n збільшується:

O(log n)


510
2018-02-21 22:22



"Зверніть увагу, як кожен рівень містить подвійне число вузлів у порівнянні з рівнем вище (отже, бінарним)" Це невірно. Те, що ви описуєте, є a збалансований бінарне дерево. Двійкове дерево просто означає, що кожен вузол має не більше двох дітей. - Oenotria
Фактично, це дуже особливе збалансоване подвійне дерево, яке називається повним двійковим деревом. Я відредагував відповідь, але мені потрібно, щоб хтось схвалив це. - user21820
Повне двійкове дерево не потребує повного заповнення останнього рівня. Я б сказав, що "повне двійкове дерево" є більш доречним. - Mr. AJ
Ваша відповідь намагається конкретніше реагувати на початкову проблему ОП, тому вона краще, ніж поточна прийнята відповідь (IMO), але вона все ще дуже неповна: ви просто даєте половину прикладу та 2 зображення ... - nbro
Це дерево містить у ньому 31 елемент, а не 16. Чому це називається набором даних з 16 елементів? Кожен вузол на ньому представляє число, інакше це буде неефективним двійкове дерево: P - Perry Monschau


O(log N) в основному це означає, що час піднімається лінійно, в той час як n піднімається експоненціально. Отже, якщо це займе 1 друге, щоб обчислити 10 елементи, це займе 2 секунд, щоб обчислити 100 елементи 3 секунд, щоб обчислити 1000 елементи тощо.

Це є O(log n) коли ми поділяємо і підкорюємо тип алгоритмів, наприклад, двійковий пошук. Іншим прикладом є швидкий сортування, коли кожен раз ми розділяємо масив на дві частини і кожного разу, коли це потрібно O(N) час, щоб знайти стрижневий елемент. Звідси це N O(log N) 


464
2018-02-21 20:18



Три рядки мудрості, яка б'є всі інші відповіді есе ... :) Тільки у випадку, якщо хтось його пропускає, в контексті програмування база журналу - 2 (не 10), тому O (log n) масштабується як 1 сек за 10 елементи, 2 сек. для 20, 3 для 40 і т.д. - nawfal
Погоджений, лаконічний та чіткий, хоча кінцевим питанням від ОП було, як визначити логарифмічну функцію, а не зовсім "що це" - Adam
Так, логарифмічна функція - це зворотна експоненціальна функція. ((log x) база a) є зворотним (потужність x). Якісний аналіз цих функцій з графіками дасть більше інтуїції. - overexchange
Це забрало мене близько 3 читання, щоб зрозуміти, що це не є помилкою. Час піднімається лінійно, в той час як кількість елементів є експоненціальним. Це означає більше елементів за менший час. Це психічно оподатковується для тих, хто візуалізує log як знайома крива брехні на графіку. - Qix
Я думаю, що це дуже хороша відповідь, за винятком тієї частини, де він стверджує, що бінарний пошук - це алгоритм розбиття та перемоги. Це не так. - code_dredd


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

Двійкове дерево - це той випадок, коли проблема розміру n розділена на підпроблему розміру n / 2, доки ми не досягнемо задачі розміру 1:

height of a binary tree

І ось, як ви отримаєте O (log n) - це сума роботи, яку потрібно виконати на вищезгаданому дереві, щоб досягти рішення.

Загальний алгоритм з O (log n) складністю часу - це Бінарний пошук, рекурсивне співвідношення якого є T (n / 2) + O (1), тобто на кожному наступному рівні дерева ви розділяєте проблему на половину і виконуєте постійну кількість додаткової роботи.


198
2017-10-26 19:33



Новачок тут Отже, чи можна сказати, що висота дерева - це розподіл за рекурсією, щоб досягти розміру n = 1? - Cody


Якщо у вас була функція, яка виконує:

1 millisecond to complete if you have 2 elements.
2 milliseconds to complete if you have 4 elements.
3 milliseconds to complete if you have 8 elements.
4 milliseconds to complete if you have 16 elements.
...
n milliseconds to complete if you have 2**n elements.

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


121
2018-02-21 20:11



Чи є log2 (n) таким же, як o (log n)? - Sven van den Boogaart
Так, подивіться коментар nawfal для відповіді на іншу відповідь: (copy-paste) - в контексті програмування база журналу 2 (не 10), тому O (log n) масштабує як 1 сек для 10 елементів, 2 сек для 20 , 3 для 40 і т. Д - Andrejs


Огляд

Інші дали хороші приклади діаграм, наприклад, діаграми дерев. Я не бачив ніяких простих прикладів коду. Таким чином, крім мого пояснення, я надам деякі алгоритми з простими твердженнями для друку, щоб проілюструвати складність різних категорій алгоритмів.

По-перше, ви хочете мати загальне уявлення про логарифм, з якого ви можете отримати https://en.wikipedia.org/wiki/Logarithm . Використання природознавства e і природний журнал. Технічні учні будуть використовувати log_10 (база журналу 10), і комп'ютерні вчені будуть використовувати log_2 (база журналу 2), оскільки комп'ютери базуються на двійковій системі. Іноді ви побачите скорочення природного журналу як ln(), інженери зазвичай залишають _10 і просто використовують log() і log_2 скорочено як lg(). Усі типи логарифмів зростають аналогічним чином, тому вони мають однакову категорію log(n).

Коли ви дивитесь на наведені нижче приклади коду, рекомендую подивитися на O (1), потім O (n), тоді O (n ^ 2). Після того, як ти з ними добре, подивіться на інших. Я включив чисті приклади, а також варіанти, щоб продемонструвати, наскільки тонкі зміни можуть призвести до однакової класифікації.

Ви можете думати про O (1), O (n), O (logn) і т. Д. Як класи або категорії зростання. Деякі категорії займуть більше часу, ніж інші. Ці категорії допомагають нам замовити алгоритм роботи. Деякі виросли швидше, оскільки вхід n зростає. Наведена нижче таблиця демонструє зростання кількості чисельно. У наведеній нижче таблиці подумайте про log (n) як стелю log_2.

enter image description here

Прості приклади коду різних великих O Категорії:

O (1) - Приклади постійного часу:

  • Алгоритм 1:

Алгоритм 1 друкує привіт один раз, і він не залежить від n, тому він завжди буде працювати в постійному часі, так що це O(1).

print "hello";
  • Алгоритм 2:

Алгоритм 2 друкує Привіт 3 рази, однак це не залежить від розміру вводу. Навіть коли росте число n, цей алгоритм завжди буде друкувати привіт лише 3 рази. Це, як кажуть 3, є постійною, тому цей алгоритм також є O(1).

print "hello";
print "hello";
print "hello";

O (log (n)) - логарифмічні приклади:

  • Алгоритм 3 - це діє як "log_2"

Алгоритм 3 демонструє алгоритм, який працює в log_2 (n). Зверніть увагу, що операція post для циклу для множини поточного значення i до 2, так i йде від 1 до 2 до 4 до 8 до 16 до 32 ...

for(int i = 1; i <= n; i = i * 2)
  print "hello";
  • Алгоритм 4 - це діє як "log_3"

Алгоритм 4 демонструє log_3. Зверніть увагу i йде від 1 до 3 до 9 до 27 ...

for(int i = 1; i <= n; i = i * 3)
  print "hello";
  • Алгоритм 5 - це діє як "log_1.02"

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

for(double i = 1; i < n; i = i * 1.02)
  print "hello";

O (n) - Приклади лінійного часу:

  • Алгоритм 6

Цей алгоритм простий, який надруковує привіт n разів.

for(int i = 0; i < n; i++)
  print "hello";
  • Алгоритм 7

Цей алгоритм показує варіант, де він буде друкувати hello n / 2 разів. n / 2 = 1/2 * н. Ми ігноруємо константу 1/2 і бачимо, що цей алгоритм має O (n).

for(int i = 0; i < n; i = i + 2)
  print "hello";

O (n * log (n)) - nlog (n) Приклади:

  • Алгоритм 8

Подумайте про це як поєднання O(log(n)) і O(n). Гніздування для циклів допомагає нам отримати O(n*log(n))

for(int i = 0; i < n; i++)
  for(int j = 1; j < n; j = j * 2)
    print "hello";
  • Алгоритм 9

Алгоритм 9 схожий на алгоритм 8, але кожна з циклів дозволила варіації, які як і раніше призводять до кінцевого результату O(n*log(n))

for(int i = 0; i < n; i = i + 2)
  for(int j = 1; j < n; j = j * 3)
    print "hello";

O (n ^ 2) - n квадратів Приклади:

  • Алгоритм 10

O(n^2) Легко отримується гніздом стандарту для петлі.

for(int i = 0; i < n; i++)
  for(int j = 0; j < n; j++)
    print "hello";
  • Алгоритм 11

Подібно до алгоритму 10, але з деякими варіаціями.

for(int i = 0; i < n; i++)
  for(int j = 0; j < n; j = j + 2)
    print "hello";

O (n ^ 3) - n cubed Приклади:

  • Алгоритм 12

Це подібно до алгоритму 10, але з 3 петлями замість 2.

for(int i = 0; i < n; i++)
  for(int j = 0; j < n; j++)
    for(int k = 0; k < n; k++)
      print "hello";
  • Алгоритм 13

Подібно до алгоритму 12, але з деякими варіаціями, які все ще дають O(n^3).

for(int i = 0; i < n; i++)
  for(int j = 0; j < n + 5; j = j + 2)
    for(int k = 0; k < n; k = k + 3)
      print "hello";

Резюме

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


108
2018-04-26 22:50



Чудово. Найкраще пояснення, яке я коли-небудь бачив. Було б краще, якщо O(n^2) відзначається як комбінація з O(n) і O(n), так O(n) * O(n) = O(n * n) = O(n^2). Це відчуваєш, як трохи стрибає без цього рівняння. Це повторення попереднього пояснення, але я думаю, що це повторення може забезпечити більшу довіру читачам для розуміння. - Eonil
@james дякую за дивовижні відповіді - Asthme
Це просто найкраще пояснення. - Edgar Kiljak


Логарифмічний час роботи (O(log n)) істотно означає, що час роботи зростає пропорційно логарифм від розміру вводу - як приклад, якщо 10 елементів займає максимум певну кількість часу xі 100 предметів займає не більше, скажімо, 2x, і більше 10000 елементів 4x, то він виглядає як O(log n) складність часу.


84
2018-02-21 20:10



log2 або log10 не має значення. Вони відрізняються лише масштабним чинником, що робить їх однакового порядку, тобто вони все ще ростуть з однаковою швидкістю. - Noldorin
Цікава річ про логарифми полягає в тому, що при порівнянні відносної висоти точна база, яку ви використовуєте, не має значення. log 10,000 / log 100 2, незалежно від того, на якій базі ви використовуєте. - Anon.
Щоб бути недоступним, O (lg n) означає, що час виконання є не більше пропорційний lg n. Те, що ви описуєте, є тета (lg n).
@ rgrig: Це правда. Я відредагував у кількох "на мостах", щоб вказати верхній зв'язок природи big-O. - Anon.
@rgrig він описав і О, і тету: Theta (lg n) означає O (lg n) - klochner