Когда запись Big-O терпит неудачу?

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

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

var topicId = xmlhttp.responseText;
var fDelayed = function(tid) {
  return function() {
    postinsql(tid);
  };
}
setTimeout(fDelayed(topicId),4000);

или короткое:

var topicId = xmlhttp.responseText;
setTimeout(function(tid) {
  return function() { postinsql(tid); };
}(topicId), 4000);
22
задан Jonas Kölker 10 June 2009 в 10:30
поделиться

17 ответов

Одна из областей, в которой происходит сбой Big O, - это шаблоны доступа к памяти. Big O учитывает только те операции, которые необходимо выполнить - он не может отслеживать, приводит ли алгоритм к большему количеству промахов в кэше или данных, которые необходимо выгружать с диска. При малых значениях N эти эффекты обычно преобладают. Например, линейный поиск в массиве из 100 целых чисел, вероятно, превзойдет поиск в двоичном дереве из 100 целых чисел из-за доступа к памяти, даже если двоичное дерево, скорее всего, потребует меньше операций. Каждый узел дерева приведет к пропуску кеш-памяти, тогда как линейный поиск чаще всего попадет в кеш для каждого поиска.

9
ответ дан 29 November 2019 в 03:15
поделиться

When your data doesn't fit the model, big-o notation will still work, but you're going to see an overlap from best and worst case scenarios.

Also, some operations are tuned for linear data access vs. random data access, so one algorithm while superior in terms of cycles, might be doggedly slow if the method of calling it changes from design. Similarly, if an algorithm causes page/cache misses due to the way it access memory, Big-O isn't going to going to give an accurate estimate of the cost of running a process.

Apparently, as I've forgotten, also when N is small :)

1
ответ дан 29 November 2019 в 03:15
поделиться

Этот вопрос похож на вопрос: «Когда IQ человека терпит неудачу на практике?» Понятно, что высокий IQ не означает, что вы добьетесь успеха в жизни, а низкий IQ не означает, что вы погибнете. Тем не менее, мы измеряем IQ как средство оценки потенциала, даже если он не абсолютный.

В алгоритмах обозначение Big-Oh дает вам IQ алгоритма. Это не обязательно означает, что алгоритм будет работать лучше всего в вашей конкретной ситуации, но есть некоторая математическая основа, которая говорит, что этот алгоритм имеет хороший потенциал. Если бы нотации Big-Oh было достаточно для измерения производительности, вы бы увидели намного больше и меньше тестирования во время выполнения.

Думайте о Big-Oh как о диапазоне, а не о конкретной мере того, что лучше или хуже. Там' s лучшие и худшие сценарии, а также огромный набор промежуточных сценариев. Выбирайте свои алгоритмы по тому, насколько хорошо они подходят для диапазона Big-Oh, но не полагайтесь на обозначения как на абсолютные значения для измерения производительности.

1
ответ дан 29 November 2019 в 03:15
поделиться

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

Для малых n два алгоритма могут быть сопоставимы. Чем больше n, тем лучше работает более умный алгоритм. Но в какой-то момент n становится настолько большим, что система поддается нехватке памяти, и в этом случае происходит «хуже». алгоритм может работать лучше, потому что константы по существу сбрасываются.

Однако это не особенно интересно. К тому времени, когда вы достигнете этой точки инверсии, производительность обоих алгоритмов обычно будет неприемлемой, и вам нужно будет найти новый алгоритм, который имеет более дружественный шаблон доступа к памяти И лучшую сложность большого O.

2
ответ дан 29 November 2019 в 03:15
поделиться

The general answer is that Big-O allows you to be really sloppy by hiding the constant factors. As mentioned in the question, the use of Fibonacci Heaps is one example. Fibonacci Heaps do have great asymptotic runtimes, but in practice the constants factors are way too large to be useful for the sizes of data sets encountered in real life.

Fibonacci Heaps are often used in proving a good lower bound for asymptotic complexity of graph-related algorithms.

Another similar example is the Coppersmith-Winograd algorithm for matrix multiplication. It is currently the algorithm with the fastest known asymptotic running time for matrix multiplication, O(n2.376). However, its constant factor is far too large to be useful in practice. Like Fibonacci Heaps, it's frequently used as a building block in other algorithms to prove theoretical time bounds.

3
ответ дан 29 November 2019 в 03:15
поделиться

Одна из обширных областей, где нотация Big-Oh не работает, - это когда объем данных превышает доступный объем ОЗУ.

Используя сортировку в качестве примера, время, необходимое для сортировки, составляет не преобладает количество сравнений или перестановок (из которых O (n log n) и O (n), соответственно, в оптимальном случае). Количество времени во многом зависит от количества операций с диском: записи блока и чтения блока.

Чтобы лучше анализировать алгоритмы, которые обрабатывают данные, превышающие доступную RAM, была создана модель ввода-вывода, в которой вы подсчитываете количество диск читает. При этом вы учитываете три параметра:

  • количество элементов, N;
  • объем памяти (ОЗУ), M (количество элементов, которые могут быть в памяти); и
  • размер дискового блока, B (количество элементов в блоке).

Примечательно, что отсутствует объем дискового пространства; это рассматривается, как если бы оно было бесконечным. Типичным дополнительным предположением является то, что M> B 2 .

Продолжая пример сортировки, вы обычно предпочитаете сортировку слиянием в случае ввода-вывода: разделите элементы на куски размером θ (M) и выполните сортировку их в памяти (например, с помощью быстрой сортировки). Затем объедините θ (M / B) из них, прочитав первый блок из каждого фрагмента в память, поместите все элементы в кучу и несколько раз выберите самый маленький элемент, пока вы не выберете B из них. Напишите этот новый блок слияния и продолжайте. Если вы когда-нибудь исчерпаете один из блоков, которые считываете в память, прочтите новый блок из того же фрагмента и поместите его в кучу.

(Все выражения следует читать как большие θ). Вы формируете N / M отсортированных блоков, которые затем объединяете. Вы объединяете журнал (база M / B) N / M раз; каждый раз, когда вы читаете и записываете все блоки N / B, так что это займет у вас N / B * (база журнала M / B из N / M) времени.

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

Эти знания любезно предоставлены моим курсом по алгоритмам ввода-вывода, проведенным Арджем и Бродалом ( http://daimi.au.dk/~large/ioS08/ ); Я также проводил эксперименты, подтверждающие теорию: сортировка кучи занимает «почти бесконечное» время, как только вы превышаете объем памяти. Быстрая сортировка становится невыносимо медленной, сортировка слиянием едва сносно медленной, сортировка слиянием с эффективным вводом-выводом работает хорошо (лучшее из всех).

Эти знания любезно предоставлены моим курсом по алгоритмам ввода-вывода, проведенным Арджем и Бродалом ( http://daimi.au.dk/~large/ioS08/ ); Я также проводил эксперименты, подтверждающие теорию: сортировка кучи занимает «почти бесконечное» время, как только вы превышаете объем памяти. Быстрая сортировка становится невыносимо медленной, сортировка слиянием едва сносно медленной, сортировка слиянием с эффективным вводом-выводом работает хорошо (лучшее из всех).

Эти знания любезно предоставлены моим курсом по алгоритмам ввода-вывода, проведенным Арджем и Бродалом ( http://daimi.au.dk/~large/ioS08/ ); Я также проводил эксперименты, подтверждающие теорию: сортировка кучи занимает «почти бесконечное» время, как только вы превышаете объем памяти. Быстрая сортировка становится невыносимо медленной, сортировка слиянием едва сносно медленной, сортировка слиянием с эффективным вводом-выводом работает хорошо (лучшее из всех).

2
ответ дан 29 November 2019 в 03:15
поделиться
  1. Маленький N - А для современных компьютеров 100, вероятно, слишком мало, чтобы беспокоиться.
  2. Скрытые множители - IE слияние против быстрой сортировки.
  3. Патологические случаи - опять же, слияние или быстрое
3
ответ дан 29 November 2019 в 03:15
поделиться

Big O не говорит, например, что алгоритм A работает быстрее, чем алгоритм B. Можно сказать, что время или пространство, используемое алгоритмом A, увеличивается с другой скоростью, чем алгоритм B, когда вход растет. Однако для любого конкретного входного размера нотация большого O ничего не говорит о производительности одного алгоритма по сравнению с другим.

Например, A может быть медленнее на операцию, но иметь больший O, чем B. более производительный для меньшего ввода, но если размер данных увеличивается, будет некоторая точка отсечки, где A становится быстрее. Big-O сам по себе ничего не говорит о том, где находится точка отсечения.

4
ответ дан 29 November 2019 в 03:15
поделиться

Одним из примеров (в котором я не являюсь экспертом) является то, что симплексные алгоритмы для линейного программирования имеют экспоненциальную сложность наихудшего случая для произвольных входных данных, хотя они хорошо работают на практике. Интересным решением этой проблемы является рассмотрение «сглаженной сложности», которая сочетает производительность в наихудшем и среднем случае путем рассмотрения небольших случайных возмущений произвольных входных данных.

Spielman and Teng (2004) смогли показать, что Симплексный алгоритм теневых вершин имеет полиномиально сглаженную сложность.

7
ответ дан 29 November 2019 в 03:15
поделиться
  1. Для большинства алгоритмов существует «средний случай» и «наихудший случай». Если ваши данные обычно попадают в «наихудший» сценарий, возможно, что другой алгоритм, теоретически менее эффективный в среднем случае, может оказаться более эффективным для ваших данных.

  2. Некоторые алгоритмы также имеют лучшие случаи, когда ваши данные могут извлекать выгоду. Например, некоторые алгоритмы сортировки имеют ужасную теоретическую эффективность, но на самом деле работают очень быстро, если данные уже отсортированы (или почти так). Другой алгоритм, теоретически более быстрый в общем случае, может не использовать тот факт, что данные уже отсортированы, и на практике работает хуже.

  3. Для очень маленьких наборов данных иногда алгоритм, который имеет лучшую теоретическую эффективность, может оказаться менее эффективным из-за большого значения «k».

8
ответ дан 29 November 2019 в 03:15
поделиться

Big-O описывает эффективность / сложность алгоритма и не обязательно время выполнения реализации данного блока кода. Это не значит, что Big-O терпит неудачу. Это просто означает, что он не предназначен для прогнозирования времени выполнения.

Посмотрите ответ на этот вопрос , чтобы получить отличное определение Big-O.

9
ответ дан 29 November 2019 в 03:15
поделиться

каноническим примером является Quicksort, у которого худшее время O (n ^ 2), а у Heapsort - O (n logn). однако на практике Quicksort обычно быстрее, чем Heapsort. Зачем? две причины:

  • каждая итерация Quicksort намного проще, чем Heapsort. Более того, его легко оптимизировать с помощью простых стратегий кэширования.

  • в худшем случае очень сложно попасть.

Но ИМХО, это никоим образом не означает «большой сбой». первый фактор (время итерации) легко включить в ваши оценки. в конце концов, большие числа O следует умножать на этот почти постоянный факт.

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

14
ответ дан 29 November 2019 в 03:15
поделиться

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

17
ответ дан 29 November 2019 в 03:15
поделиться

Когда N мало, преобладает постоянный коэффициент. Искать элемент в массиве из пяти элементов, вероятно, быстрее, чем искать его в хеш-таблице.

27
ответ дан 29 November 2019 в 03:15
поделиться

Он терпит неудачу ровно в одном случае: когда люди пытаются использовать его для чего-то, для чего он не предназначен .

Он сообщает вам, как масштабируется алгоритм. Он не говорит вам, насколько он быстр.

Нотация Big-O не говорит вам, какой алгоритм будет быстрее в любом конкретном случае. Это только говорит вам, что при достаточно большом вводе один будет быстрее другого.

104
ответ дан 29 November 2019 в 03:15
поделиться

Это в некоторой степени зависит от того, что измеряет Big-O - в худшем случае он обычно «терпит неудачу», так как производительность во время выполнения будет намного лучше, чем предполагает Big-O. Если это средний случай, то все может быть намного хуже.

Нотация Big-O обычно "терпит неудачу", если входные данные алгоритма содержат некоторую априорную информацию. Часто нотация Big-O относится к наихудшему случаю сложности - что часто случается, если данные являются либо полностью случайными, либо полностью неслучайными.

Например, если вы вводите данные в алгоритм, который профилирован, и большой -o основан на рандомизированных данных, но ваши данные имеют очень четко определенную структуру, время получения результатов может быть намного быстрее, чем ожидалось. Точно так же, если вы измеряете среднюю сложность,

4
ответ дан 29 November 2019 в 03:15
поделиться

Краткий ответ: всегда на современном оборудовании, когда вы начинаете использовать много памяти. Учебники предполагают, что доступ к памяти единообразен, и это уже не так. Вы, конечно, можете провести анализ Big O для неоднородной модели доступа, но это несколько сложнее.

Маленькие n случаев очевидны, но не интересны: достаточно быстро - достаточно быстро.

На практике у меня были проблемы с использованием стандартных коллекций в Delphi, Java, C # и Smalltalk с несколькими миллионами объектов. И с меньшими, где доминирующим фактором оказалась хеш-функция или сравнение

0
ответ дан 29 November 2019 в 03:15
поделиться
Другие вопросы по тегам:

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