Big O, як ви його обчислюєте / наближаєте?

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

Але мені цікаво, як ви обчислюєте або наближаєте складність ваших алгоритмів?

1, але, як то кажуть, не перестарайтеся, передчасна оптимізація - це корінь усього зла , і оптимізація без обґрунтованої причини також заслуговує цього імені.

722
06 авг. заданий sven 06 Серпня. 2008-08-06 13:18 '08 о 13:18 2008-08-06 13:18
@ 23 відповідей

Я асистент викладача в своєму місцевому університеті на курсах Data Structures and Algorithms. Я зроблю все можливе, щоб пояснити це тут на простих термінах, але будьте обережні, щоб ця тема змушувала моїх учнів на пару місяців, нарешті, зрозуміти. Більш детальну інформацію ви знайдете в розділі 2 Data Structures and Algorithms in Java .


Немає механічної процедури яка може використовуватися для отримання BigOh.

Як "кулінарна книга", щоб отримати обчислювальної складності цієї функції

 Number_Of_Steps = f(N) 

Отже, ми маємо f(N) , функцію для підрахунку кількості кроків обчислення. Введення функції - це розмір структури для обробки. Це означає, що ця функція називається так:

 Number_Of_Steps = f(data.length) 

Параметр N приймає значення data.length . Тепер нам потрібно фактичне визначення функції f() . Це робиться з вихідного коду, в якому кожна цікава рядок пронумерована від 1 до 4.

Існує безліч способів обчислення BigOh. З цього моменту ми будемо припускати, що кожне речення, яке не залежить від розміру вхідних даних, приймає постійні числові кроки C .

Ми збираємося додати індивідуальне число кроків функції, і ні оголошення локальної змінної, ні оператор return не залежить від розміру масиву data .

Це означає, що рядки 1 і 4 приймають C кількість кроків кожен, а функція приблизно така:

 f(N) = C + ??? + C 

Наступна частина повинна визначити значення оператора for . Пам'ятайте, що ми підраховуємо кількість обчислювальних кроків, що означає, що тіло оператора for виконується N раз. Те ж, що і додавання C , N раз:

 f(N) = C + (C + C + ... + C) + C = C + N * C + C 

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

Щоб отримати фактичний BigOh, нам потрібен Асимптотический аналіз функції. Це приблизно робиться наступним чином:

  • Приберіть все константи C .
  • З f() отримаєте polyomium в standard form .
  • Розділіть члени многочлена та відсортуйте їх за швидкістю зростання.
  • Тримайте ту, яка росте більше, коли N наближається до infinity .

Наше f() має два члена:

 f(N) = 2 * C * N ^ 0 + 1 * C * N ^ 1 

Прибираємо все константи C і надлишкові частини:

 f(N) = 1 + N ^ 1 

Оскільки останній член є тим, який росте більше, коли f() наближається до нескінченності (думайте про обмеження ), це аргумент BigOh, і функція sum() має значення BigOh:

 O(N) 

Є кілька трюків для вирішення деяких складних завдань: використовуйте sumations , коли зможете.

Як приклад цей код можна легко вирішити за допомогою підсумовування:

 for (i = 0; i < 2*n; i += 2) { // 1 for (j=n; j > i; j--) { // 2 foo(); // 3 } } 

Перше, що вам потрібно було запитати, це порядок виконання foo() . У той час як звичайний повинен бути O(1) , вам потрібно запитати своїх професорів про це. O(1) означає (майже, в основному) константу C , незалежно від розміру N .

Оператор for для пропозиції номер один складний. Поки індекс закінчується на 2 * N , приріст виконується двома. Це означає, що перший for отримує виконані тільки кроки N , і нам потрібно розділити рахунок на два.

 f(N) = Summation(i from 1 to 2 * N / 2)( ... ) = = Summation(i from 1 to N)( ... ) 

Пропозиція номер два ще більш складне, оскільки воно залежить від значення i . Погляньте: індекс я приймає значення: 0, 2, 4, 6, 8, ..., 2 * N, а другий for виконується: N раз перший, N - 2 другий, N - 4 третій ... до етапу N / 2, на якому другий for ніколи не буде виконано.

За формулою це означає:

 f(N) = Summation(i from 1 to N)( Summation(j = ???)( ) ) 

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

 f(N) = Summation(i from 1 to N)( Summation(j = 1 to (N - (i - 1) * 2)( C ) ) 

(Ми припускаємо, що foo() є O(1) і приймає кроки C .)

У нас є проблема: коли i приймає значення N / 2 + 1 вгору, внутрішнє підсумовування закінчується негативним числом! Це неможливо і неправильно. Нам потрібно розділити підсумовування навпіл, будучи точкою повороту, момент i приймає N / 2 + 1 .

 f(N) = Summation(i from 1 to N / 2)( Summation(j = 1 to (N - (i - 1) * 2)) * ( C ) ) + Summation(i from 1 to N / 2) * ( C ) 

Оскільки ключовий момент i > N / 2 , внутрішній for не буде виконано, і ми припускаємо постійну складність виконання C на його тілі.

Тепер суми можна спростити, використовуючи деякі правила ідентифікації:

  • Підсумовування (w від 1 до N) (C) = N * C
  • Підсумовування (w від 1 до N) (A (+/-) B) = підсумовування (w від 1 до N) (A) (+/-) підсумовування (w від 1 до N) (B)
  • Підсумовування (w від 1 до N) (w * C) = C * підсумовування (w від 1 до N) (w) (C - постійна, яка не залежить від w )
  • Підсумовування (w від 1 до N) (w) = (N * (N + 1)) / 2

Застосування деякої алгебри:

 f(N) = Summation(i from 1 to N / 2)( (N - (i - 1) * 2) * ( C ) ) + (N / 2)( C ) f(N) = C * Summation(i from 1 to N / 2)( (N - (i - 1) * 2)) + (N / 2)( C ) f(N) = C * (Summation(i from 1 to N / 2)( N ) - Summation(i from 1 to N / 2)( (i - 1) * 2)) + (N / 2)( C ) f(N) = C * (( N ^ 2 / 2 ) - 2 * Summation(i from 1 to N / 2)( i - 1 )) + (N / 2)( C ) => Summation(i from 1 to N / 2)( i - 1 ) = Summation(i from 1 to N / 2 - 1)( i ) f(N) = C * (( N ^ 2 / 2 ) - 2 * Summation(i from 1 to N / 2 - 1)( i )) + (N / 2)( C ) f(N) = C * (( N ^ 2 / 2 ) - 2 * ( (N / 2 - 1) * (N / 2 - 1 + 1) / 2) ) + (N / 2)( C ) => (N / 2 - 1) * (N / 2 - 1 + 1) / 2 = (N / 2 - 1) * (N / 2) / 2 = ((N ^ 2 / 4) - (N / 2)) / 2 = (N ^ 2 / 8) - (N / 4) f(N) = C * (( N ^ 2 / 2 ) - 2 * ( (N ^ 2 / 8) - (N / 4) )) + (N / 2)( C ) f(N) = C * (( N ^ 2 / 2 ) - ( (N ^ 2 / 4) - (N / 2) )) + (N / 2)( C ) f(N) = C * (( N ^ 2 / 2 ) - (N ^ 2 / 4) + (N / 2)) + (N / 2)( C ) f(N) = C * ( N ^ 2 / 4 ) + C * (N / 2) + C * (N / 2) f(N) = C * ( N ^ 2 / 4 ) + 2 * C * (N / 2) f(N) = C * ( N ^ 2 / 4 ) + C * N f(N) = C * 1/4 * N ^ 2 + C * N 

І BigOh:

 O(N²) 
 O(N²) 
1340
31 янв. відповідь дан vz0 31 Січня. 2011-01-31 18:33 '11 о 18:33 2011-01-31 18:33

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

Кілька прикладів того, як він використовується в коді C.

Скажімо, у нас є масив з n елементів

 int array[n]; 

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

 x = array[0]; 

Якби ми хотіли знайти число в списку:

border=0
 for(int i = 0; i < n; i++){ if(array[i] == numToFind){ return i; } } 

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

Коли ми отримуємо вкладені цикли:

 for(int i = 0; i < n; i++){ for(int j = i; j < n; j++){ array[j] += 2; } } 

Це O (n ^ 2), так як для кожного проходу зовнішнього циклу (O (n)) нам потрібно знову пройти весь список, щоб n помножити на нас з квадратом n.

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

184
06 авг. відповідь дан DShook 06 Серпня. 2008-08-06 16:34 '08 о 16:34 2008-08-06 16:34

Хоча знання того, як визначити час Big O для вашої конкретної проблеми, корисно, знаючи, що деякі загальні випадки можуть значно допомогти вам прийняти рішення в вашому алгоритмі.

Ось деякі з найбільш поширених випадків, знятих з http://en.wikipedia.org/wiki/Big_O_notation#Orders_of_common_functions :

O (1) - визначення того, чи є число парних або непарних; використовуючи таблицю пошуку по постійному розміром або хеш-таблицю

O (logn) - Пошук елемента в відсортованому масиві з двійковим пошуком

O (n) - пошук елемента в несортовані списку; додавання двох n-значних чисел

O (n 2) - множення двох n-значних чисел на простий алгоритм; додавання двох матриць n × n; сортування бульбашок або сортування вставки

O (n 3) - Множення двох n × n-матриць простим алгоритмом

O (c n) - Пошук (точного) вирішення проблеми комівояжера за допомогою динамічного програмування; визначення того, чи є два логічних оператора еквівалентними з використанням грубої сили

O (n!) - Рішення проблеми комівояжера за допомогою пошуку грубої сили

O (n n) - Часто використовується замість O (n!) Для отримання більш простих формул для асимптотичної складності

83
05 сент. відповідь дан Giovanni Galbo 05 сент. 2008-09-05 22:09 '08 о 22:09 2008-09-05 22:09

Маленьке нагадування: позначення big O використовується для позначення асимптотической складності (тобто коли розмір проблеми зростає до нескінченності), і він приховує константу.

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

Зверніть увагу, що прихована константа дуже сильно залежить від реалізації!

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

Існують різні тимчасові складнощі:

  • Найгірший випадок (зазвичай найпростіший спосіб з'ясувати, хоча і не завжди дуже значимий)
  • Середній розмір (зазвичай набагато складніше з'ясувати)

  • ...

Гарне введення - це введення в аналіз алгоритмів Р. Седжуїк і П. Флейолета.

Як ви говорите, premature optimisation is the root of all evil і (якщо можливо) профілювання дійсно має завжди використовуватися при оптимізації коду. Це може навіть допомогти вам визначити складність ваших алгоритмів.

38
23 авг. відповідь дан OysterD 23 Серпня. 2008-08-23 23:43 '08 о 23:43 2008-08-23 23:43

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

Також я хотів би додати, як це робиться для рекурсивних функцій:

припустимо, що у нас є функція типу ( код схеми ):

 (define (fac n) (if (= n 0) 1 (* n (fac (- n 1))))) 

який рекурсивно обчислює факторіал даного числа.

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

Таким чином, продуктивність для тіла: O (1) (константа).

Потім спробуйте і визначте це для кількості рекурсивних викликів. У цьому випадку ми маємо n-1 рекурсивних викликів.

Таким чином, продуктивність для рекурсивних викликів: O (n-1) (порядок n, оскільки ми викидаємо несуттєві частини).

Потім помістіть ці два разом, і тоді ви отримаєте продуктивність для всієї рекурсивної функції:

1 * (n-1) = O (n)


Peter , щоб відповісти на ваші підняті питання; метод, який я описую тут, фактично обробляє це досить Що ж. Але майте на увазі, що це все ще наближення, а не повний математично правильну відповідь. Описаний тут метод також є одним з методів навчання в університеті, і якщо я правильно пам'ятаю, він використовувався для більш просунутих алгоритмів, ніж факторіал, використаний в цьому прикладі. Звичайно, все залежить від того, наскільки добре ви можете оцінити час роботи тіла функції і кількість рекурсивних викликів, але це справедливо і для інших методів.

25
07 авг. відповідь дан sven 07 Серпня. 2008-08-07 11:10 '08 об 11:10 2008-08-07 11:10

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

O ((n / 2 + 1) * (n / 2)) = O (n 2/4 + n / 2) = O (n 2/4) = O (n 2)

Це не працює для нескінченних рядів, зауважте. У загальному випадку немає єдиного рецепту, хоча для деяких поширених випадків застосовуються наступні нерівності:

O (log N) O (N) O (N log N) O (N 2) <O (N k) <O (e n) <O (п!)

23
31 янв. відповідь дан Marcelo Cantos 31 Січня. 2011-01-31 16:30 '11 о 16:30 2011-01-31 16:30

Я думаю про це з точки зору інформації. Будь-яка проблема полягає у вивченні певної кількості біт.

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

Наприклад, оператор if , має дві гілки, однаково ймовірні, має ентропію 1/2 * log (2/1) + 1/2 * log (2/1) = 1/2 * 1 + 1/2 * 1 = 1. Таким чином, його ентропія дорівнює 1 біт.

Припустимо, що ви шукаєте таблицю з N елементів, наприклад N = 1024. Це 10-бітна проблема, тому що log (1024) = 10 біт. Тому, якщо ви можете шукати його за допомогою операторів IF, які мають однаково ймовірні результати, він повинен приймати 10 рішень.

Що ви отримуєте з бінарним пошуком.

Припустимо, що ви виконуєте лінійний пошук. Ви дивіться на перший елемент і питаєте, чи хоче він той, який ви хочете. Ймовірності - 1/1024, що і є, і 1023/1024, що це не так. Ентропія цього рішення становить 1/1024 * log (1024/1) + 1023/1024 * log (1024/1023) = 1/1024 * 10 + 1023/1024 * близько 0 = близько 0,01 біт. Ви дізналися дуже мало! Друге рішення не набагато краще. Ось чому лінійний пошук настільки повільний. Фактично це експоненціально в кількості біт, яке вам потрібно вивчити.

Припустимо, ви робите індексування. Припустимо, що таблиця попередньо відсортована в безліч бункерів, і ви використовуєте деякі з усіх біт в ключі, щоб індексувати безпосередньо в записи таблиці. Якщо є 1024 бункера, ентропія становить 1/1024 * log (1024) + 1/1024 * log (1024) + ... для всіх 1024 можливих результатів. Це 1/1024 * 10 раз 1024 результату або 10 біт ентропії для цієї операції індексування. Ось чому пошук індексування виконується швидко.

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

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

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

18
10 марта '09 в 16:24 2009-03-10 16:24 відповідь дан Mike Dunlavey 10 березня '09 о 16:24 2009-03-10 16:24

Давайте почнемо з початку.

Перш за все, прийміть принцип, що деякі прості операції з даними можна зробити в O(1) часу, тобто в часі, яке не залежить від розміру введення. Ці примітивні операції в C складаються з

  • Арифметичні операції (наприклад, + або%).
  • Операції порівняння (наприклад, <=).
  • Операції доступу до структури (наприклад, індексування масиву, таке як A [i] або покажчик fol- за допомогою оператора →).
  • Просте призначення, таке як копіювання значення в змінну.
  • Виклик функцій бібліотеки (наприклад, scanf, printf).

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

  • Оператори присвоювання, які не включають виклики функцій в їх висловах.
  • Читання тверджень.
  • Записувати оператори, які не вимагають виклику функцій для обчислення аргументів.
  • Оператори переходу переривають, продовжують, goto і повертають вираз, де вираз не містить виклику функції.

У C багато for-loops формуються шляхом ініціалізації індексної змінної до деякого значення і збільшуючи цю змінну на 1 кожен раз навколо циклу. Контур for-loop закінчується, коли індекс досягає певної межі. Наприклад, for-loop

 for (i = 0; i < n-1; i++) { small = i; for (j = i+1; j < n; j++) if (A[j] < A[small]) small = j; temp = A[small]; A[small] = A[i]; A[i] = temp; } 

використовує індексний змінну i. Він збільшує я на 1 кожен раз навколо циклу, і ітерації зупиніться, коли я досягне n - 1.

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

Наприклад, for-loop виконує ітерацію ((n − 1) − 0)/1 = n − 1 times , так як 0 є початковим значенням i, n - 1 є найвищим значенням, що досягається я (тобто коли i досягає n -1, цикл зупиняється і не відбувається ітерації з я = n-1), а 1 додається до я на кожній ітерації циклу.

У найпростішому випадку, коли час, проведений в тілі циклу, однаково для кожного ітерації ми можемо помножити велику верхню межу тіла на кількість часу навколо циклу. Строго кажучи, ми повинні тоді додати O (1) час для ініціалізації індекс циклу і час O (1) для першого порівняння індексу циклу з limit, тому що ми тестуємо ще раз, ніж ми обходимо цикл. Однак, якщо можна виконати нульові часи циклу, час для ініціалізації циклу і тесту межа один раз є молодшим членом, який можна відкинути за правилом підсумовування.


Тепер розглянемо цей приклад:

 (1) for (j = 0; j < n; j++) (2) A[i][j] = 0; 

Ми знаємо, що рядок (1) займає час O(1) . Ясно, что мы идем вокруг цикла n раз, так как мы можем определить, вычитая нижний предел из верхнего предела, найденного на линии (1), а затем добавление 1. Так как тело, строка (2), принимает время O (1), можно пренебречь время для увеличения j и время для сравнения j с n, оба из которых также O (1). Таким образом, время выполнения строк (1) и (2) является <сильным > произведением n и O (1), которое O(n) .