Я изучаю время работы в нотации Big O и амортизированное время. Я понимаю понятие O(n) линейного времени, означающее, что размер входных данных влияет на рост алгоритма пропорционально... и то же самое касается, например, квадратичного времени O(n2) и т.д... даже алгоритмы, такие как генераторы перестановок, с O(n!) временем, которое растет по факториалам.
Например, следующая функция является O(n), потому что алгоритм растет пропорционально своему входу n:
f(int n) {
int i;
for (i = 0; i < n; ++i)
printf("%d", i);
}
Аналогично, если бы был вложенный цикл, то время было бы O(n2).
Но что именно является O(log n)? Например, что значит сказать, что высота полного двоичного дерева равна O(log n)?
Я знаю (может быть, не очень подробно), что такое логарифм, в том смысле, что: log10 100 = 2, но я не могу понять, как определить функцию с логарифмическим временем.
Я не могу понять, как определить функцию с временным лагом.
Наиболее общие свойства логарифмической работает функция заключаются в том, что:
или
Именно поэтому, например, при поиске людей в телефонной книге является o(зарегистрируйте N). Вы Don'т нужно проверить любую ранее человека в телефонной книге, чтобы найти правильный один; вместо этого вы можете просто "разделяй и властвуй", глядя на основе, где их имена в алфавитном порядке, и в каждом разделе вы только должны исследовать подмножество каждого раздела, прежде чем вы в конечном итоге найти кого-то's номер телефона.
Конечно, большая телефонная книга по-прежнему будет считать вас больше времени, но он выиграл'т расти так же быстро, как пропорциональное увеличение размера.
<ч/>
Мы можем расширить примере телефонной книги, чтобы сравнить другие виды операций и their время. Мы будем считать нашу телефонная книга businesses (в "желтых страницах", У), которые имеют уникальные имена и people (в "белые страницы" У), которые не могут иметь уникальные имена. Номер телефона присваивается не более одного человека или бизнеса. Мы также будем предполагать, что она занимает постоянное время, чтобы перевернуть к конкретной странице.
Здесь представлены времена выполнения некоторых операций мы можем выполнить на телефонной книге, от лучшего к худшему:
О(1) (лучшем случае): учитывая, что страницы бизнес's имя и название компании, найти по номеру телефона.
О(1) (в среднем случае): учитывая странице, что человек's имя на и имя, найти номер телефона.
*O(зарегистрируйте N): дано человеку's имя, найти номер телефона путем случайного выбора точки О на полпути через часть книги вы еще'т искали, то проверка того, что человек's имя на тот момент. Повторите процесс примерно на полпути через часть книги, где человек's имя лжи. (Это бинарный поиск человека's имя.)
О(н): найти всех людей, чьи телефонные номера содержат цифры на "5 и".
О(н): дали номер телефона, найти человека или бизнес с этим номером.
О(n записей N): существует путаница в принтере'ы офис, и наши телефонной книги у всех его страниц вставлены в случайном порядке. Исправить заказ, так что это's правильное, глядя на имя на каждой странице и затем положить эту страницу в соответствующем месте в новую, пустую телефонную книгу.
Для приведенных ниже примеров, мы'вновь теперь на принтере's в офисе. Телефонные книги ждут, чтобы быть отправлены по почте каждому жителю или бизнес, и там'ы наклейки на каждой телефонной книги с указанием, когда он должен быть отправлен. Каждый человек или бизнес получает одну телефонную книгу.
О(n записей N): мы хотим, чтобы персонализировать телефонный справочник, да мы're собирается найти каждого человека или бизнеса's имя на свои места скопировать, затем круг их имя в книге и написать короткое благодарственное письмо за покровительство.
О(п<SUP-серфинг и GT;2</суп>): ошибка произошла в офисе, и каждой записи в каждой из книг есть дополнительная с "0" и в конце номер телефона. Взять немного белого и удалить каждый ноль.
О(н &ампер;мидот; Н!): Мы'вновь готовы загрузить телефонную книгу на пароходной пристани. К сожалению, робот, который, как предполагалось загрузить книги пошли наперекосяк: он'ы ставить книги на грузовик в случайном порядке! Даже хуже, он загружает все книги на грузовик, а затем проверяет, чтобы увидеть, если они're в правильном порядке, а если нет, он разгружает их и начинает сначала. (Это страшный Бого рода.)
О(п<SUP-серфинг и GT;п</SUP-серфинг>): вам починить робота так, чтобы он's нагрузка все правильно. На следующий день, один из ваших коллег играет шутку на вас и провода погрузочной платформе робот для автоматизированной системы печати. Каждый раз, когда робот идет, чтобы загрузить оригинальную книгу, фабрики принтера делает повторяющийся запуск все телефонные книги! К счастью, робот's ошибка. системы обнаружения достаточно искушены, что робот не'т попробуйте выполнить печать еще более экземплярах при обнаружении дубликат книги для загрузки, но для загрузки все оригинал и дубликат книги, что'ы были напечатаны.
Для более математического объяснения вы можете оформить заказ как сложность времени прибывает в Журнала N
здесь. https://hackernoon.com/what-does-the-time-complexity-o-log-n-actually-mean-45f94bb5bfbf
Много хороших ответов уже отвечал на этот вопрос, но я считаю, что мы действительно не хватает важного - а именно, иллюстрированный ответ.
что это значит сказать, что высота полного бинарного дерева является o(зарегистрируйте N)?
Следующий чертеж изображает бинарное дерево. Обратите внимание, как каждый уровень содержит двойное количество узлов по сравнению с уровнем выше (отсюда бинарные):
Бинарный поиск пример со сложностью o(зарегистрируйте N)
. Позвольте'ы сказать, что узлы в нижней части дерева на рис. 1 представлены элементы в некоторых отсортированной коллекции. Бинарный поиск-это разделяй и властвуй алгоритм, и чертеж показывает, как нам нужно (в большинстве) 4 сравнения, чтобы найти запись, которую мы ищем в этом наборе 16 элементов.
Предположим, что мы имели вместо набора данных с 32 элементами. Далее на чертеже выше, чтобы найти, что теперь нам понадобится 5 сравнения, чтобы найти то, что мы ищем, как дерево растет на один уровень глубже, когда мы умножили количество данных. В результате, сложность алгоритма может быть описана логарифмической последовательности.
Планирую журнал(N)` на простом листе бумаги, будет результат в виде графика, где наблюдается рост кривой замедляет как увеличивается п:
O(зарегистрируйте N)
в основном означает, что время идет линейно, а " н " идет в геометрической прогрессии. Так что если он принимает 1
во-вторых, чтобы вычислить 10
элементов, это займет 2
секунд, чтобы вычислить 100
элементов 3
секунд, чтобы вычислить 1000
элементов, и так далее.
Это o(зарегистрируйте N)
, когда мы делаем разделяй и властвуй типа алгоритмов электронной.г двоичный поиск. Другой пример быстрой сортировки, где каждый раз мы делим массив на две части и каждый раз, когда он берет о(n) времени, чтобы найти поворотный элемент. Следовательно, это Н o(зарегистрируйте N)
Ниже объяснение на примере полностью сбалансированный бинарное дерево, чтобы помочь вам понять, как мы получим логарифмическую сложность.
Бинарное дерево-это случай, когда задача размером n разбивается на суб-проблемы размера n/2, пока мы не достигнем проблема размер 1:
И что's, как вы получите o(зарегистрируйте N), который является объем работы, который нужно сделать на ветке выше, чтобы достичь решения.
Общий алгоритм с O(зарегистрируйте N) сложность времени бинарного поиска, чьи рекурсивное соотношение Т(П/2) + О(1), т. е. на каждом уровне дерева вы проблему разделить на половину и сделать постоянное количество дополнительных работ.
Обзор
Другие дали положительные примеры диаграмм, таких как диаграммы дерева. Я не вижу никаких простых примеров кода. Так что помимо моих объяснений, я'будете предоставить некоторые алгоритмы с простой печати заявления, чтобы проиллюстрировать сложность различных категорий алгоритму.
Во-первых, вы'll хочу иметь общее понятие логарифма, которое вы можете получить от https://en.wikipedia.org/wiki/Logarithm . Естественные науки используют е и натуральный логарифм. Инженерно ученики будут использовать log_10 (логарифма по основанию 10) и компьютер ученые будут использовать log_2 (основание логарифма 2) много, так как компьютеры являются двоичными основе. Иногда вы'll увидеть аббревиатуры натуральный логарифм, как функция LN (), инженеры обычно оставляют _10 и журналов используйте ()
и log_2 сокращенно ЛГ()
. Все виды логарифмов расти подобным образом, поэтому они имеют те же категории журнал(N)
.
Когда вы посмотрите на примеры ниже код, я рекомендую посмотреть в O(1), затем o(n), то о(п^2). После того, как вы хорошо с этим, то смотрите на других. Я'ве включены чистые примеры, а также варианты, чтобы показать, как небольшие изменения все же может привести к той же классификации.
Вы можете думать о(1), О(П), О(logn), то и т. д. Как классы или категории роста. Некоторые категории займет больше времени, чем другим. Эти категории помогают дать нам заказ на выполнение алгоритма. Некоторые росли быстрее в качестве входных данных N растет. Следующая таблица демонстрирует рост численно. В таблице ниже думаю лог(N) в качестве потолка log_2.
Простых Примерах Различных Больших Категории, О:
О(1) - Постоянные Времени Примеры:
Алгоритм 1 отпечатки привет некогда и он не'т зависеть от N, так что она всегда будет выполняться за постоянное время, так Это О(1)
.
print "hello";
Алгоритм 2 отпечатки привет 3 раза, однако это не зависит от размера входных данных. Даже при увеличении N, этот алгоритм всегда будет печатать только "Привет" 3 раза. Это, как говорится 3, является постоянным, поэтому этот алгоритм является также о(1)
.
print "hello";
print "hello";
print "hello";
О(лог(Н)) - логарифмические примеры:
Алгоритм 3 представляет собой алгоритм, который работает в log_2(Н). Обратите внимание на пост работа для петель кратно текущее значение i на 2, так что " я " идет от 1 до 2 до 4 до 8 до 16 до 32 ...
for(int i = 1; i <= n; i = i * 2)
print "hello";
Алгоритм 4 демонстрирует log_3. Заметьте, " я " идет от 1 до 3 до 9 до 27...
for(int i = 1; i <= n; i = i * 3)
print "hello";
Алгоритм 5 это важно, так как помогает показать, что пока число больше 1, а результат многократно умножились против себя, что вы смотрите на логарифмический алгоритм.
for(double i = 1; i < n; i = i * 1.02)
print "hello";
О(n) - линейные примеры время:
Этот алгоритм прост, которая печатает "привет" N раз.
for(int i = 0; i < n; i++)
print "hello";
Этот алгоритм показан вариант, где он будет печатать привет в N/2 раз. н/2 = 1/2 * Н. Мы игнорируем 1/2 постоянный и видеть, что этот алгоритм является o(n) времени.
for(int i = 0; i < n; i = i + 2)
print "hello";
*О(нлог(Н)) - nlog(Н) примеры:**
Думайте об этом как сочетание о(лог(н))
и o(Н)
. Вложенность циклов помочь нам получить О(Н*лог(Н))
for(int i = 0; i < n; i++)
for(int j = 1; j < n; j = j * 2)
print "hello";
9 алгоритм как алгоритм 8, но каждая из петель позволило вариации, которые по-прежнему приводят в конечном итоге-о(н*лог(Н))`
for(int i = 0; i < n; i = i + 2)
for(int j = 1; j < n; j = j * 3)
print "hello";
О(N^2) - н в квадрате примеры:
О(N^2)
легко получены за счет вложения стандартная для петель.
for(int i = 0; i < n; i++)
for(int j = 0; j < n; j++)
print "hello";
Подобный алгоритм 10, но с некоторыми вариациями.
for(int i = 0; i < n; i++)
for(int j = 0; j < n; j = j + 2)
print "hello";
О(N^3) - н примеры в кубе:
Это как алгоритм 10, но с 3 петли вместо 2.
for(int i = 0; i < n; i++)
for(int j = 0; j < n; j++)
for(int k = 0; k < n; k++)
print "hello";
Подобный алгоритм 12, но с некоторыми вариациями, что еще урожай О(N^3)
.
for(int i = 0; i < n; i++)
for(int j = 0; j < n + 5; j = j + 2)
for(int k = 0; k < n; k = k + 3)
print "hello";
Резюме
Выше приведем несколько примеров прямо вперед, и варианты, чтобы помочь продемонстрировать, что небольшие изменения могут быть введены, что действительно Дон't изменить анализа. Надеюсь, это дает вам достаточное представление.
Если у вас есть функция, которая принимает:
1 millisecond to complete if you have 2 elements.
2 milliseconds to complete if you have 4 elements.
3 milliseconds to complete if you have 8 elements.
4 milliseconds to complete if you have 16 elements.
...
n milliseconds to complete if you have 2**n elements.
Затем он берет журнал<суб и GT;2</суб>(N) времени. В Большой о нотации, грубо говоря, означает, что отношения нужны только, чтобы быть правдой для больших n, и постоянных факторов и меньшие сроки могут быть проигнорированы.
Логарифмическое время работы (O(log n)
) означает, что время работы растет пропорционально логарифму размера входных данных - в качестве примера, если 10 элементов занимают максимум некоторое количество времени x
, 100 элементов занимают максимум, скажем, 2x
, а 10 000 элементов занимают максимум 4x
, то это выглядит как временная сложность O(log n)
.
Логарифм
Ок, давайте'ы попробовать и полностью понять, что такое логарифм на самом деле.
Представьте, у нас есть веревка, и мы привязали его к лошади. Если веревка напрямую связана с лошадью, заставить лошадь должна тянуть далеко (скажем, человека) непосредственно 1.
А теперь представьте веревку петлей вокруг шеста. Лошадь вам сейчас придется тянуть много раз сложнее. Количество раз будет зависеть от шершавости веревки и размер поляк, но позвольте'ы предположить, что это будет умножить один'с прочность на 10 (когда веревка делает полный оборот).
Теперь если трос один раз петляли, лошади должны тянуть в 10 раз сложнее. Если человек решает сделать это очень трудным для лошади, он может снова петлей веревку вокруг шеста, увеличивая его'с прочность на 10 раз. Третий цикл будет снова увеличить силу еще 10 раз.
Мы видим, что для каждого цикла, значение увеличивается на 10. Число витков, необходимое для получения любого числа называют логарифм числа, т. е. нам нужно 3 сообщения на несколько по 1000 раз, 6 постов, чтобы умножить свои силы на 1000000.
3-логарифм 1000, а 6-логарифм 1,000,000 (по основанию 10).
Так что o(зарегистрируйте N) на самом деле означает?
В нашем примере выше, наш 'темп роста' Это O(зарегистрируйте N). За каждые дополнительные петли, сила наша веревка может обрабатывать в 10 раз больше:
Turns | Max Force
0 | 1
1 | 10
2 | 100
3 | 1000
4 | 10000
n | 10^n
Теперь приведенный выше пример не использовал основанию 10, но, к счастью, основание журнала является незначительным, когда мы говорим о больших нотации о.
Теперь давайте'ы представьте, что вы пытаетесь угадать число от 1-100.
Your Friend: Guess my number between 1-100!
Your Guess: 50
Your Friend: Lower!
Your Guess: 25
Your Friend: Lower!
Your Guess: 13
Your Friend: Higher!
Your Guess: 19
Your Friend: Higher!
Your Friend: 22
Your Guess: Lower!
Your Guess: 20
Your Friend: Higher!
Your Guess: 21
Your Friend: YOU GOT IT!
Теперь вам понадобилось 7 попыток, чтобы получить это право. Но какая связь здесь? Каково наибольшее количество элементов, которые можно догадаться из каждого дополнительного угадать?
Guesses | Items
1 | 2
2 | 4
3 | 8
4 | 16
5 | 32
6 | 64
7 | 128
10 | 1024
Используя график, мы видим, что если мы будем использовать бинарный поиск, чтобы угадать число от 1-100 нам потребуется по самые 7 попыток. Если бы у нас было 128 цифры, можно угадать число в 7 попытки но 129 номеров переносит нас по самые 8 попыток (в отношении логарифмов, здесь нам понадобится 7 попыток на 128 диапазон значений, 10 догадки на 1024 диапазон значений. 7 он логарифм 128, 10-логарифм 1024 (база 2)).
Обратите внимание, что я жирным шрифтом 'максимум'. Нотация Big-O всегда относится к худшему случаю. Если вы'вновь повезло, вы смогли угадать число в одной попытке и так в лучшем случае за O(1), но это'ы другая история.
мы видим, что для каждого угадать наш набор данных сокращается. Хорошее эмпирическое правило, чтобы определить, если алгоритм имеет время logarithmtic это , Чтобы увидеть, если набор данных сокращается в определенном порядке после каждой итерации
Что о o(n записей N)?
Вы в конечном итоге прийти через некоторое время linerarithmic за o(n журнал(N) алгоритм. При этом, как правило, выше опять-таки применяется, но в этот раз логарифмической функции должен выполняться N раз, например, сократить размер списка Н раз, который происходит в алгоритмы, как сортировка слиянием.
Вы можете легко определить, если алгоритмическом Время N записей N. Искать внешний цикл, который перебирает список (О(Н)). Потом посмотрите, если есть внутренний цикл. Если внутренняя петля резка/уменьшения набор данных на каждой итерации, что петля (o(зарегистрируйте N), и поэтому общий алгоритм = о(n записей N).
Предупреждение: веревка-логарифм пример отхватили от отличный математика'с наслаждением книге У. Сойер.
Вы можете думать o(зарегистрируйте N) интуитивно, говоря, что время пропорционально количеству цифр В Н.
Если операцию выполняет постоянное время работы над каждой цифрой или бита входа, вся операция займет время, пропорциональное числу разрядов или битов на входе, а не величины входного сигнала; таким образом, o(зарегистрируйте N) а не за o(n) времени.
Если операцию делает серию из постоянной времени решения каждой из которых половинки (уменьшается с коэффициентом 3, 4, 5..) размер входных данных должны рассматриваться, всего потребуется время, пропорциональное логарифму по основанию 2 (основание 3, основание 4, основание 5 и т. п.) размера n входных данных, а не о(n).
И так далее.
Лучший способ я'ве всегда приходилось мысленно представлять алгоритм, который работает за o(зарегистрируйте N) выглядит следующим образом:
Если вы увеличить размер проблемы в мультипликативной суммы (т. е. умножить ее размер на 10), работы увеличилось только на количестве присадок.
Применяя это к вашему двоичном вопрос так у вас есть хорошее применение: если вы удвоите количество узлов в бинарном дереве, высота увеличивается только на 1 (количество присадок). Если вы снова удвоить его, он еще только увеличивается на 1. (Очевидно, я'м предполагая, что он остается сбалансированным и такие). Этак, вместо того, чтобы удваивать вашу работу, когда размер проблемы умножатся, вы'повторно только делает очень немного больше работы. Что's, почему o(зарегистрируйте N) алгоритмы являются удивительными.
Сначала я рекомендую вам прочитать следующие книги;
Вот некоторые функции и их ожидал сложностей. Цифры указывают заявление частота исполнения.
Следующие алгоритмическую сложность диаграммы также взяты из bigocheatsheet
Наконец, очень простой витриной есть показывает, как он рассчитывается;
Анатомия программы заявление частота исполнения.
Анализ времени выполнения программы (пример).
что'журналы<суб>б</суб>(Н)?
Это количество раз вы можете вырезать входа длины n раз на б равных частей до достижения сечения размер 1.
Разделяй и властвуй алгоритмов обычно дошла
компонент на время работы. Это происходит от повторного падения на входе.
В случае бинарного поиска, на каждой итерации вы выбросите половину входа. Следует отметить, что в Биг-О'нотации, журнал логарифма по основанию 2.
Редактировать: как уже отмечалось, основание логарифма не'т имеет значения, но для получения большой производительности алгоритма, фактор журнала выйдет из вдвое, следовательно, почему я думаю о нем, как основание 2.
но что именно является o(зарегистрируйте N)? Например, что это значит сказать, что высота >полная бинарное дерево является o(зарегистрируйте N)?
Я бы перефразировал это как 'высота полного двоичного дерева журнала n'. Полагая, что высота полного двоичного дерева будет o(зарегистрируйте N), если ты, проходя вниз Шаг за шагом.
Я не могу понять, как определить функции с логарифмической время.
Логарифм является, по сути, обратное возведение в степень. Так, если каждый 'шаг' ваша функция устранения коэффициент элементов из исходного пункта, что является логарифмический алгоритм время.
На примере дерева, вы можете легко увидеть, что спускается уровень сокращения узлов вниз экспоненциального числа элементов, как вы будете продолжать обход. Популярный пример, глядя через имя-сортировка телефонного справочника является, по сути, эквивалентно спускаемся вниз бинарное дерево поиска (в центре страницы-это корневой элемент, и вы можете вывести на каждом шагу, стоит ли идти влево или вправо).
Эти 2 случая потребует o(журнал N) время
case 1: f(int n) {
int i;
for (i = 1; i < n; i=i*2)
printf("%d", i);
}
case 2 : f(int n) {
int i;
for (i = n; i>=1 ; i=i/2)
printf("%d", i);
}
O(зарегистрируйте N) является немного вводит в заблуждение, точнее это's с O(зарегистрируйте<суб>2</суб> п), т. е. (логарифм с основанием 2).
Высота сбалансированного бинарного дерева равна o(журнал<суб и GT;2</суб> п), так как каждый узел имеет два (обратите внимание на "два" и как в журнале<суб и GT;2</суб> п) дочерние узлы. Так, дерево с N вершинами имеет высоту журнала<суб>2</суб> п.
Другим примером является бинарный поиск, который имеет время выполнения о(журнал<суб>2</суб> п) потому что на каждом шагу вам разделить пространство поиска на 2.
O(зарегистрируйте N)
относится к функции (или алгоритм, или шаг в алгоритме) работы на промежуток времени, пропорциональный логарифму (как правило, основание 2, в большинстве случаев, но не всегда, и в любом случае это несущественно, с большой-о нотации*) от размера входных данных.
Логарифмическая функция является обратной по отношению к показательной функции. Иными словами, если ваш вклад растет в геометрической прогрессии (а не линейно, как обычно считают), ваша функция растет линейно.
Выполняется за o(зарегистрируйте N), время являются очень распространенными в какой-либо "разделяй и властвуй" приложение, потому что вы (в идеале) резка работы в каждую половину времени. Если в каждой дивизии или покорить шаги, вы делаете постоянную работу (или работу, которая не является константой времени, но со временем растут медленнее, чем o(зарегистрируйте N)
), то вся функция o(зарегистрируйте N)
. Это'ы довольно часто каждый шаг требует линейного времени на вместо ввода; это составит в общей сложность-о(n записей N)`.
Работающем сложность бинарного поиска-это пример o(зарегистрируйте N)
. Это потому, что в бинарный поиск, вы всегда игнорируете половину вашего вклада в каждый из последующих шагов путем деления массива пополам и фокусируемся только на одной половине с каждым шагом. Каждый шаг-постоянная времени, потому что в двоичном поиска вам понадобится лишь сравнить один элемент с ключом, чтобы выяснить, что делать дальше независимо от того, насколько большой массив вы рассматриваете в любой момент. Так вы же примерно журнал(N)/журнал(2) шагов.
Работает временная сложность сортировки слиянием является примером о(n записей N)
. Это потому, что вы деления массива пополам с каждым шагом, в результате чего в общей сложности около журнал(N)/журнал(2) шагов. Однако, в каждом шаге нужно выполнить операции объединения всех элементов (будь то's одна операция слияния на два подсписка из N/2 элементов, или две операции объединения на четыре подсписки из N/4 элементов, не имеет значения, потому что это добавляет к тому, чтобы сделать это для n элементов в каждом шаге). Таким образом, общая сложность-о(n записей N)`.
*Помните, что большой-о нотации, но <а href="и http://en.wikipedia.org/wiki/Big_O_notation#Formal_definition">по определению</а> константы Дон'т вопрос. Также в <а href="и http://en.wikipedia.org/wiki/Change_of_base_formula_for_logs#Changing_the_base">изменение базы правил</а> для логарифмов, единственная разница между логарифмами различных баз является постоянным фактором.
Это просто означает, что время, необходимое для этой задачи, растет с log(n) (пример: 2 с для n = 10, 4 с для n = 100, ...). Для получения более точных сведений читайте статьи Википедии Алгоритм двоичного поиска и Нотация Big O.
Проще говоря: на каждом шаге алгоритма вы можете сократить работу наполовину. (Асимптотически эквивалентны третьей, четвертой, ...)
Если вы построите график логарифмической функции на графический калькулятор или что-то подобное, вы'увидите, что она действительно поднимается медленно-даже медленнее, чем линейная функция.
Вот почему алгоритмы с логарифмической временной сложностью высоко ценятся: даже для очень больших n (пусть'ы говорим, что N = 10^8, например), они выполняют более чем приемлемо.