Питання з тегом 'big-o'

Позначення Big-O використовується для представлення асимптотических оцінок зверху. У ньому описується відповідна складність часу або простору алгоритмів. Аналіз Big-O забезпечує грубу і спрощену оцінку проблемних проблем.
39
відповідей

Що таке просте англійське пояснення "Big O"?

Я волів би якомога менше формального визначення і просту математику.
заданий 28 Січня. '09 о 14:10
31
відповідь

Що означає O (log n)?

В даний час я вивчаю час роботи Big O Notation і час амортизації. Я розумію поняття лінійного часу O (n), що означає, що розмір введення впливає на зростання алгоритму пропорційно ... і те ж саме стосується, наприклад, квадратичного часу ...
заданий 21 февр. '10 о 23:05
23
відповідей

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

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

Постійне амортизоване час

Що означає "Постійне амортизоване час", коли мова йде про тимчасову складності алгоритму?
заданий 14 Жовтня. '08 в 11:32
9
відповідей

У чому різниця між Θ (n) і O (n)?

Іноді я бачу Θ (n) з дивним символом Θ з чимось посеред нього, а іноді просто O (n). Це просто лінь друкувати, бо ніхто не знає, як набирати цей символ, або це означає щось інше?
заданий 23 Січня. '09 о 1:58
34
відповідей

Чи існують які-небудь O (1 / n) алгоритми?

Чи існують які-небудь O (1 / n) алгоритми? Або що-небудь ще менше, ніж O (1)?
заданий 25 травня '09 о 9:15
25
відповідей

Big-O для восьмирічних дітей?

Я питаю більше про те, що це означає для мого коду. Я розумію поняття математично, мені просто нелегко обернути голову навколо того, що вони мають на увазі концептуально. Наприклад, якщо хтось повинен виконати операцію O (1) в структурі даних, я ...
заданий 20 сент. '08 в 7:59
12
відповідей

Обчислювальна складність послідовності Фібоначчі

Я розумію запис Big-O, але я не знаю, як обчислити її для багатьох функцій. Зокрема, я намагався з'ясувати обчислювальну складність наївною версії послідовності Фібоначчі: int Fibonacci (int n) {if (n <= 1) return n; else ...
заданий 11 дек. '08 о 23:20
4
відповідей

Список функцій Big-O для PHP

Після використання PHP на деякий час я помітив, що не всі PHP вбудовані в функції так швидко, як очікувалося. Розглянемо нижче дві можливі реалізації функції, яка знаходить, якщо число є простим, використовуючи кеш масив простих ч ...
заданий 19 березня '10 в 2:12
22
відповідей

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

Чи існують випадки, коли ви віддаєте перевагу O (log n) складність за часом для O (1) тимчасової складності? Або O (n) до O (log n)? Чи є у вас приклади?
заданий 09 дек. '15 о 16:25
3
відповідей

Різниця між примітками Big-O і Little-O

У чому різниця між нотами Big-O O (n) і Маленька-O нотація O (n)?
заданий 01 сент. '09 о 23:22
14
відповідей

Додати об'єкт до списку в R в амортизувати постійному часу, O (1)?

Якщо у мене є список R mylist, ви можете додати до нього елемент obj так: mylist [[length (mylist) +1]] <- obj Але, звичайно, є ще більш компактний спосіб. Коли я був новим в R, я пробував писати lappend () наступним чином: lappend <-...
заданий 13 березня '10 о 3:14
32
відповідей

Як знайти k-й найбільший елемент в несортовані масиві довжини n в O (n)?

Я вважаю, що є спосіб знайти k-й найбільший елемент в несортовані масиві довжини n в O (n). Або, можливо, це "очікувалося" O (n) або щось ще. Як ми можемо це зробити?
заданий 31 Жовтня. '08 в 0:06
9
відповідей

Чи є log (n!) = Θ (n · log (n))?

Я повинен показати, що log (n!) = Θ (n · log (n)). Було дано вказівку, що я повинен показати верхню межу з nn і показати нижню межу з (n / 2) (n / 2). Це здається мені нецікавим. Чому це так? Я можу впевнено побачити, як перетворити ...
заданий 19 Січня. '10 о 20:15
5
відповідей

Чи є 2 ^ n і n * 2 ^ n однаковою тимчасової складністю?

Ресурси, які я виявив по тимчасовій складності, неясно, коли можна ігнорувати терміни в рівнянні складності часу, зокрема, з не-поліноміальними прикладами. Мені ясно, що, з огляду на що-то виду n 2 + n + 1, останні два члена несущест ...
заданий 13 февр. '14 о 23:32