почему три разных обозначения временной сложности [дубликат]

Вместо того, чтобы бросать код на вас, есть два понятия, которые являются ключом к пониманию того, как JS обрабатывает обратные вызовы и асинхронность. (это даже слово?)

Модель цикла события и параллелизма

Есть три вещи, о которых вам нужно знать; Очередь; цикл события и стек

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

while (queue.waitForMessage()) {
   queue.processNextMessage();
}

Как только он получает сообщение для запуска чего-то, он добавляет его в очередь. Очередь - это список вещей, которые ждут выполнения (например, ваш запрос AJAX). Представьте себе это так:

 1. call foo.com/api/bar using foobarFunc
 2. Go perform an infinite loop
 ... and so on

Когда одно из этих сообщений будет исполнено, оно выталкивает сообщение из очереди и создает стек, стек - это все, что нужно выполнить JS для выполнения инструкции в сообщение. Таким образом, в нашем примере ему говорят позвонить foobarFunc

function foobarFunc (var) {
  console.log(anotherFunction(var));
}

. Так что все, что foobarFunc должно выполнить (в нашем случае anotherFunction), будет вставлено в стек. исполняемый, а затем забытый - цикл события затем переместится на следующую вещь в очереди (или прослушивает сообщения)

. Главное здесь - порядок выполнения. Это

КОГДА что-то будет запущено

Когда вы совершаете вызов с использованием AJAX для внешней стороны или выполняете любой асинхронный код (например, setTimeout), Javascript зависит от ответ, прежде чем он сможет продолжить.

Большой вопрос, когда он получит ответ? Ответ в том, что мы не знаем, поэтому цикл событий ждет, когда это сообщение скажет: «Эй, забери меня». Если JS просто ждал этого сообщения синхронно, ваше приложение замерзнет, ​​и оно сосать. Таким образом, JS продолжает выполнение следующего элемента в очереди, ожидая, пока сообщение не будет добавлено обратно в очередь.

Вот почему с асинхронной функциональностью мы используем вещи, называемые обратными вызовами. Это похоже на обещание буквально. Как и в I , обещание что-то вернуть в какой-то момент jQuery использует специальные обратные вызовы, называемые deffered.done deffered.fail и deffered.always (среди других). Вы можете увидеть их все здесь

Итак, вам нужно передать функцию, которая в какой-то момент будет выполнена с переданными ей данными.

Поскольку обратный вызов не выполняется немедленно, но в более позднее время важно передать ссылку на функцию, которую она не выполнила. поэтому

function foo(bla) {
  console.log(bla)
}

, поэтому большую часть времени (но не всегда) вы пройдете foo не foo()

. Надеюсь, это будет иметь смысл. Когда вы сталкиваетесь с такими вещами, которые кажутся запутанными, я настоятельно рекомендую полностью прочитать документацию, чтобы хотя бы понять ее. Это сделает вас намного лучшим разработчиком.

379
задан igaurav 30 September 2014 в 10:46
поделиться

9 ответов

Краткое объяснение:

Если алгоритм имеет значение Θ (g (n)), это означает, что время работы алгоритма с ростом n (размер ввода) становится пропорциональным g (n).

Если алгоритм имеет O (g (n)), это означает, что время работы алгоритма с ростом n больше не более , пропорциональное g (n).

Обычно, даже когда люди говорят о O (g (n)), они фактически означают Θ (g (n)), но технически, есть разница.


Более технически:

O (n) представляет верхнюю границу. Θ (n) означает жесткую привязку. Ω (n) - нижняя граница.

f (x) = Θ (g (x)), если f (x) = O (g (x)) и f (x ) = Ω (g (x))

В основном, когда мы говорим, что алгоритм имеет O (n), это также O (n2), O (n1000000), O (2n), ... но алгоритм Θ (n) не является Θ (n2).

На самом деле, поскольку f (n) = Θ (g (n)) означает для достаточно больших значений n, f (n) могут быть связаны в пределах c1g (n) и c2g (n) для некоторых значений c1 и c2, т. е. скорость роста f асимптотически равна g: g может быть нижней границей и верхней границей of f. Это непосредственно означает, что f может быть нижней границей и верхней границей g. Следовательно,

f (x) = Θ (g (x)) iff g (x) = Θ (f (x))

для отображения f (n) = Θ (g (n)), достаточно показать, что g является верхней границей f (т. е. f (n) = O (g (n))), а f - нижняя грань g ( т.е. f (n) = Ω (g (n)), что является тем же самым, что g (n) = O (f (n))). В частности,

f (x) = Θ (g (x)), если f (x) = O (g (x)) и g (x) = O (f (x)))


Также имеются небольшие о-о и мало-омега (ω), обозначающие свободные верхние и свободные нижние границы функции.

Подводя итог:

f(x) = O(g(x)) (big-oh) означает, что скорость роста f(x) асимптотически меньше или равна к скорости роста g(x).

f(x) = Ω(g(x)) (big-omega) означает, что скорость роста f(x) асимптотически больше или равна роста скорость g(x)

f(x) = o(g(x)) (little-oh) означает, что скорость роста f(x) асимптотически меньше темпа роста g(x).

f(x) = ω(g(x)) (мало-омега) означает, что скорость роста f(x) асимптотически больше темпа роста g(x)

f(x) = Θ(g(x)) (theta) означает, что скорость роста f(x) асимптотически равна темпа роста g(x)

. Для более подробного обсуждения вы можете читайте определение в Википедии или обратитесь к классическому учебнику, например, «Введение в алгоритмы» Cormen и др.

542
ответ дан 20 revs, 4 users 91% 3 September 2018 в 15:10
поделиться
10
ответ дан ahnbizcad 3 September 2018 в 15:10
поделиться

Есть простой способ (трюк, я думаю), чтобы помнить, что обозначение означает что.

Все нотации Big-O можно считать имеющими планку.

При взгляде на Ω панель находится внизу, поэтому это (асимптотическая) нижняя граница.

Когда вы смотрите на Θ, панель, очевидно, находится посередине , Так что это (асимптотическая) плотная граница.

Когда вы пишете O, вы обычно заканчиваете вверху и рисуете скригль. Поэтому O (n) - верхняя граница функции. Справедливости ради, этот не работает с большинством шрифтов, но это оригинальное обоснование имен.

293
ответ дан Andrei Krotkov 3 September 2018 в 15:10
поделиться

Заключение: мы рассматриваем большие O, большие θ и большие Ω как одно и то же.

Почему? Я объясню причину ниже:

Во-первых, я уточню одно неправильное утверждение, некоторые люди думают, что нам просто нужна худшая временная сложность, поэтому мы всегда используем большие O вместо больших θ. Я скажу, что этот человек дерьмо. Верхняя и нижняя границы используются для описания одной функции, не используемой для описания временной сложности. Наихудшая функция времени имеет свою верхнюю и нижнюю границу; функция наилучшего времени также имеет свою верхнюю и нижнюю границы.

Чтобы четко объяснить связь между большими O и большими θ, я объясню связь между большими O и малыми o в первую очередь. Из определения легко понять, что малый о - подмножество большого О. Например:

T (n) = n ^ 2 + n, можно сказать, что T (n) = O (n ^ 2), T (n) = O (n ^ 3), T (n) = O (n ^ 4). Но при малых o T (n) = o (n ^ 2) не удовлетворяет определению малой o. Так что просто T (n) = o (n ^ 3), T (n) = o (n ^ 4) верны при малых o. Резервный T (n) = O (n ^ 2) - это что? Это большой θ!

Как правило, мы говорим, что большой O является O (n ^ 2), едва ли T (n) = O (n ^ 3), T (n ) = O (N ^ 4). Зачем? Поскольку мы рассматриваем большой O как большой θ подсознательно.

Аналогично, мы также рассматриваем большую Ω как большую θ подсознательно.

Одним словом, большие O, большие θ и большие Ω не то же самое из определений, но они одно и то же в наших ушах и мозгу.

3
ответ дан haibo cu 3 September 2018 в 15:10
поделиться

Вместо того, чтобы дать теоретическое определение, которое прекрасно описано здесь уже, я приведу простой пример:

Предположим, что время выполнения f(i) равно O(1). Ниже приведен фрагмент кода, асимптотическое время выполнения которого Θ(n). Он всегда вызывает функцию f(...) n раз. И нижняя, и верхняя граница - n.

for(int i=0; i<n; i++){
    f(i);
}

Второй фрагмент кода ниже имеет асимптотическое время выполнения O(n). Он вызывает функцию f(...) не более n раз. Верхняя граница равна n, но нижняя граница может быть Ω(1) или Ω(log(n)), в зависимости от того, что происходит внутри f2(i).

for(int i=0; i<n; i++){
    if( f2(i) ) break;
    f(i);
}
33
ответ дан kara deniz 3 September 2018 в 15:10
поделиться

один - это большой «O»

, один - Big Theta

http://en.wikipedia.org/wiki/Big_O_notation

Big O означает, что ваш алгоритм будет выполняться не более, чем в заданном выражении (n ^ 2)

Big Omega означает, что ваш алгоритм будет выполняться не меньше шагов, чем в данном выражении (n ^ 2)

Когда оба условия верны для одного и того же выражения, вы можете использовать большую тета-нотацию ....

52
ответ дан l_39217_l 3 September 2018 в 15:10
поделиться

f(n) принадлежит O(n), если существует положительный k, поскольку f(n)<=k*n

f(n) принадлежит Θ(n), если существует положительный k1, k2 как k1*n<=f(n)<=k2*n

Статья в Википедии о примечании Big O

6
ответ дан Mateen Ulhaq 3 September 2018 в 15:10
поделиться

График может облегчить понимание предыдущих ответов:

Θ-Обозначение - тот же порядок | O-Notation - верхняя граница

Θ(n) - Same order [/g8] O(n) - Upper bound [/g9]

На английском языке

Слева отметим, что существует верхняя граница и нижняя граница, которые являются одинаковыми по порядку величины (т.е. g (n) ). Игнорируем константы, и если верхняя граница и нижняя граница имеют один и тот же порядок величины, можно справедливо сказать f (n) = Θ (g (n)) или f (n) находится в большой тете g (n) .

Начиная с правого, более простого примера, говорят, что верхняя граница g (n) является просто по порядку величины и игнорирует константу c (как и все обозначения больших O ).

10
ответ дан Ricardo 3 September 2018 в 15:10
поделиться

Использование пределов

Рассмотрим f(n) > 0 и g(n) > 0 для всех n. Это нормально, потому что самый быстрый алгоритм имеет по крайней мере одну операцию и завершает ее выполнение после запуска. Это упростит исчисление, потому что вместо абсолютного значения (|f(n)|) мы можем использовать значение (f(n)).

  1. f(n) = O(g(n))

    Общее:
              f(n)     
    0 ≤ lim ──────── < ∞
        n➜∞   g(n)
    
    Для g(n) = n:
              f(n)     
    0 ≤ lim ──────── < ∞
        n➜∞    n
    
    Примеры:
        Expression               Value of the limit
    ------------------------------------------------
    n        = O(n)                      1
    1/2*n    = O(n)                     1/2
    2*n      = O(n)                      2
    n+log(n) = O(n)                      1
    n        = O(n*log(n))               0
    n        = O(n²)                     0
    n        = O(nⁿ)                     0
    
    Контрпримеры:
        Expression                Value of the limit
    -------------------------------------------------
    n        ≠ O(log(n))                 ∞
    1/2*n    ≠ O(sqrt(n))                ∞
    2*n      ≠ O(1)                      ∞
    n+log(n) ≠ O(log(n))                 ∞
    
  2. f(n) = Θ(g(n))

    Общие сведения:
              f(n)     
    0 < lim ──────── < ∞
        n➜∞   g(n)
    
    Для g(n) = n:
              f(n)     
    0 < lim ──────── < ∞
        n➜∞    n
    
    Примеры:
        Expression               Value of the limit
    ------------------------------------------------
    n        = Θ(n)                      1
    1/2*n    = Θ(n)                     1/2
    2*n      = Θ(n)                      2
    n+log(n) = Θ(n)                      1
    
    Контрпримеры:
        Expression                Value of the limit
    -------------------------------------------------
    n        ≠ Θ(log(n))                 ∞
    1/2*n    ≠ Θ(sqrt(n))                ∞
    2*n      ≠ Θ(1)                      ∞
    n+log(n) ≠ Θ(log(n))                 ∞
    n        ≠ Θ(n*log(n))               0
    n        ≠ Θ(n²)                     0
    n        ≠ Θ(nⁿ)                     0
    
2
ответ дан ROMANIA_engineer 3 September 2018 в 15:10
поделиться
Другие вопросы по тегам:

Похожие вопросы: