Вместо того, чтобы бросать код на вас, есть два понятия, которые являются ключом к пониманию того, как 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()
. Надеюсь, это будет иметь смысл. Когда вы сталкиваетесь с такими вещами, которые кажутся запутанными, я настоятельно рекомендую полностью прочитать документацию, чтобы хотя бы понять ее. Это сделает вас намного лучшим разработчиком.
Если алгоритм имеет значение Θ (g (n)), это означает, что время работы алгоритма с ростом n (размер ввода) становится пропорциональным g (n).
Если алгоритм имеет O (g (n)), это означает, что время работы алгоритма с ростом n больше не более , пропорциональное g (n).
blockquote>Обычно, даже когда люди говорят о O (g (n)), они фактически означают Θ (g (n)), но технически, есть разница.
Более технически:
O (n) представляет верхнюю границу. Θ (n) означает жесткую привязку. Ω (n) - нижняя граница.
f (x) = Θ (g (x)), если f (x) = O (g (x)) и f (x ) = Ω (g (x))
blockquote> blockquote>В основном, когда мы говорим, что алгоритм имеет 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))
blockquote>для отображения 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)))
blockquote>
Также имеются небольшие о-о и мало-омега (
ω
), обозначающие свободные верхние и свободные нижние границы функции.Подводя итог:
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)
blockquote>
f(x) = Θ(g(x))
(theta) означает, что скорость ростаf(x)
асимптотически равна темпа ростаg(x)
. Для более подробного обсуждения вы можете читайте определение в Википедии или обратитесь к классическому учебнику, например, «Введение в алгоритмы» Cormen и др.
Есть простой способ (трюк, я думаю), чтобы помнить, что обозначение означает что.
Все нотации Big-O можно считать имеющими планку.
При взгляде на Ω панель находится внизу, поэтому это (асимптотическая) нижняя граница.
Когда вы смотрите на Θ, панель, очевидно, находится посередине , Так что это (асимптотическая) плотная граница.
Когда вы пишете O, вы обычно заканчиваете вверху и рисуете скригль. Поэтому O (n) - верхняя граница функции. Справедливости ради, этот не работает с большинством шрифтов, но это оригинальное обоснование имен.
Заключение: мы рассматриваем большие O, большие θ и большие Ω как одно и то же.
Почему? Я объясню причину ниже:
Во-первых, я уточню одно неправильное утверждение, некоторые люди думают, что нам просто нужна худшая временная сложность, поэтому мы всегда используем большие O вместо больших θ. Я скажу, что этот человек дерьмо. Верхняя и нижняя границы используются для описания одной функции, не используемой для описания временной сложности. Наихудшая функция времени имеет свою верхнюю и нижнюю границу; функция наилучшего времени также имеет свою верхнюю и нижнюю границы.
Чтобы четко объяснить связь между большими O и большими θ, я объясню связь между большими O и малыми o в первую очередь. Из определения легко понять, что малый о - подмножество большого О. Например:
blockquote>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, большие θ и большие Ω не то же самое из определений, но они одно и то же в наших ушах и мозгу.
blockquote>
Вместо того, чтобы дать теоретическое определение, которое прекрасно описано здесь уже, я приведу простой пример:
Предположим, что время выполнения 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);
}
один - это большой «O»
, один - Big Theta
http://en.wikipedia.org/wiki/Big_O_notation
Big O означает, что ваш алгоритм будет выполняться не более, чем в заданном выражении (n ^ 2)
Big Omega означает, что ваш алгоритм будет выполняться не меньше шагов, чем в данном выражении (n ^ 2)
Когда оба условия верны для одного и того же выражения, вы можете использовать большую тета-нотацию ....
f(n)
принадлежит O(n)
, если существует положительный k
, поскольку f(n)<=k*n
f(n)
принадлежит Θ(n)
, если существует положительный k1
, k2
как k1*n<=f(n)<=k2*n
График может облегчить понимание предыдущих ответов:
[/g8] [/g9]
На английском языке
Слева отметим, что существует верхняя граница и нижняя граница, которые являются одинаковыми по порядку величины (т.е. g (n) ). Игнорируем константы, и если верхняя граница и нижняя граница имеют один и тот же порядок величины, можно справедливо сказать f (n) = Θ (g (n)) или f (n) находится в большой тете g (n) .
Начиная с правого, более простого примера, говорят, что верхняя граница g (n) является просто по порядку величины и игнорирует константу c (как и все обозначения больших O ).
Рассмотрим f(n) > 0
и g(n) > 0
для всех n
. Это нормально, потому что самый быстрый алгоритм имеет по крайней мере одну операцию и завершает ее выполнение после запуска. Это упростит исчисление, потому что вместо абсолютного значения (|f(n)|
) мы можем использовать значение (f(n)
).
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)) ∞
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