То, как знать, когда Большой O, Логарифмически?
решение состоит в том, чтобы использовать асинхронное ожидание, например, так: если вы хотите вызвать функцию refereshToken: let result = await refereshToken (аргумент); и функцию прототипа refereshToken, которую вы должны записать следующим образом: async refreshToken (token: JwtToken) {return this.http.post (' http://api.com/auth/refresh ', {refresh_token: token.refresh_token}). Подписаться (async (res: JwtToken) => {this.token = res; ожидать this.setToken (res); вернуть this.token;}); }
5 ответов
Не уверен, что вы это имеете в виду, но ... логарифмическая сложность обычно возникает, когда вы работаете с структура распределенных данных, подобная сбалансированному двоичному дереву, которое содержит 1 узел в корне, 2 дочерних элемента, 4 внука, 8 правнуков и т. д. В основном на каждом уровне число узлов умножается на некоторый коэффициент (2), но все же только один из них участвует в итерации. Или, в качестве другого примера, цикл, в котором индекс удваивается на каждом шаге:
for (int i = 1; i < N; i *= 2) { ... }
Подобные вещи являются сигнатурами логарифмической сложности.
Not rigorous, but it you have an algorithm that is essentially dividing the work needed to be done by half on each iteration, then you have logarithmic complexity. The classic example is binary search.
Если вы просто хотите узнать о логарифмическом Big Oh, следите за тем, чтобы ваши данные были разрезаны пополам на каждом шаге повторения.
Это потому, что если вы обрабатываете данные, которые в два раза больше как шаг перед ним, это бесконечный ряд.
Here is another way of saying it.
Suppose your algorithm is linear in the number of digits in the size of the problem. So, perhaps you have a new algorithm to factor a large number, that you can show to be linear in the number of digits. A 20 digit number thereby takes twice as long to factor as a 10 digit number using your algorithm. This would have log complexity. (And it would be worth something for the inventor.)
Bisection has the same behavior. It takes roughly 10 bisection steps to cut the interval length by a factor of 1024 = 2^10, but only 20 steps will cut the interval by a factor of 2^20.
Log complexity does not always mean an algorithm is fast on all problems. The linear factor in front of the O(log(n)) may be large. So your algorithm may be terrible on small problems, not becoming useful until the problem size is appreciably large that other algorithms die an exponential (or polynomial) death.