Как Вы показываете, что один алгоритм более эффективен, чем другой алгоритм?

Это зависит от обстоятельств. В университете вы учитесь сравнивать алгоритмы, вычисляя количество операций, которые он выполняет, в зависимости от размера / значения его аргументов. (Сравните анализ алгоритмов и нотацию большого О ). Я бы потребовал, чтобы каждый порядочный программист понимал хотя бы основы этого.

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

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

Стандартным способом сравнения различных алгоритмов является сравнение их сложности с использованием нотации Big O . На практике Вы, конечно же, сравните и алгоритмы.

В качестве примера, сортировка пузырьков и кучи алгоритмов сортировки имеет сложность O(n²) и O(n log n) соответственно.

В заключение очень трудно построить репрезентативные бенчмарки, см. эту интересную заметку Кристера Эрикссона на эту тему.

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

В терминах стандартных определений эффективности часто используется Big-0 Notation, Однако в "реальном мире" за пределами академических кругов обычно профилируют/отмечают оба уравнения, а затем сравнивают результаты

Часто бывает трудно сделать общие предположения о нотации Big-0, так как это в первую очередь связано с петлей и предполагает фиксированную стоимость кода в цикле, так что бенчмаркинг был бы лучшим способом пойти

Одна оговорка, на которую следует обратить внимание, заключается в том, что иногда результат может значительно варьироваться в зависимости от размера набора данных, с которым вы работаете - для маленького N в цикле вы иногда не найдете большой разницы

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

1) два алгоритма одного порядка сложности, назовем их f и g, оба со сложностью O(N^2) могут различаться во времени исполнения на несколько порядков величины. Большая нотация O не измеряет количество отдельных шагов, связанных с каждой итерацией, поэтому f может занять 100 шагов, в то время как g - 10.

Кроме того, различные компиляторы или языки программирования могут генерировать более или менее инструкций для каждой итерации алгоритма, а тонкий выбор в описании алгоритма может привести к тому, что кэш или процессорное оборудование будет работать в 10-1000 раз хуже, не изменяя ни порядка big-O, ни количества шагов!

2) Алгоритм O(N) может превосходить O(log(N)) алгоритм

Big-O нотация не измеряет количество отдельных шагов, связанных с каждой итерацией, поэтому если O(N) делает 100 шагов, но O(log(N)) делает 1000 шагов за каждую итерацию, то для наборов данных до определенного размера O(N) будет лучше.

К компиляторам применяются те же проблемы, что и выше.

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

Чтобы ответить на ваш вопрос: «Вы также представляете математическую функцию, или вы просто делаете скорость как скорость как алгоритмов».

Да, чтобы оба - давайте суммируемся.

Способ «Большой o», описанный выше, относится к наихудшему характеристику дела в качестве знака, упомянутой выше. «Скорость» вы упоминаете, будет способ оценить «средние результаты дела». На практике может быть большая разница между худшими характеристиками и средней производительностью. Вот почему ваш вопрос интересен и полезный.

Ухудшение эффективности случая было классическим способом определения и классификации производительности алгоритма. Совсем недавно исследования были более обеспокоены средним показателем эффективности или более точно эффективности, такие как: 99% проблем потребуют менее n. Вы можете себе представить, почему второй случай гораздо более практичен для большинства проблем.

В зависимости от приложения у вас может быть очень разные требования. Одно приложение может потребовать времени отклика менее 3 секунд 95% времени - это приведет к определению границ производительности. Другой может потребовать производительности, чтобы никогда не превышать 5 секунд - это приведет к анализу худшего дела.

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

Надеюсь, это поможет.

Большая нотация О дает вам сложность алгоритма в худшем случае, и в основном полезно знать, как вырастет алгоритм во время исполнения, когда вырастет количество данных, которые должны быть обработаны. Например (синтаксис в стиле Си, это не важно):

List<int> ls = new List<int>();           (1) O(1)
for (int i = 0; i < ls.count; i++)        (2) O(1)                                     
   foo(i);                                (3) O(log n) (efficient function)

Cost analysis:
    (1)  cost: O(1), constant cost
    (2)  cost: O(1), (int i = 0;)
               O(1), (i < ls.count)
               O(1), (i++)
               ----  total: O(1) (constant cost), but it repeats n times (ls.count)
    (3)  cost: O(log n) (assume it, just an example), 
                        but it repeats n times as it is inside the loop

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

List<int> ls = new List<int>();           (1) O(1)
for (int i = 0; i < ls.count; i++)        (2) O(1)                                     
  if ( (i mod 2) == 0) )                  (*) O(1)  (constant cost)
    foo(i);                               (3) O(log n)

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

Данные - это только примеры и могут быть неточными, просто пытаясь проиллюстрировать поведение нотации Big O. В основном это дает вам поведение вашего алгоритма, когда данные растут (ваш алгоритм будет линейным, экспоненциальным, логарифмическим, ...), но это не то, что все знают как "эффективность", или почти, это не единственное значение "эффективности".

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

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

Надеюсь, это поможет.

Вы можете легко отделаться, если есть значительная разница в классе асимптотической сложности Big-O для наихудшего или ожидаемого случая. Даже тогда вам нужно будет показать, что скрытые постоянные факторы не делают «лучший» (с асимптотической точки зрения) алгоритм медленнее для входов разумного размера.

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

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

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

Это когда другие аппаратные ресурсы или другое запущенное программное обеспечение, работающее в Parallell, вступают в игру, в том числе деталь, называемая инженерными ударами. Аппаратное обеспечение имеет свои ограничения. Память и диск являются ограниченными ресурсами. Производительность диска даже зависит от механики.

Планировщик операционной системы будет, например, дифференцировать на связанные ввода-вывода и ресурсы CPU, чтобы улучшить общую производительность для данного приложения. СУБД учитывает дисковые чтения и пишет, использование памяти и процессора и даже сетевое взаимодействие в случае кластеров.

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

Итак, я думаю, что ответ заключается в том, что разработчики используют теоретические методы, такие как BIG O и сравнительный анализ, чтобы определить скорость алгоритмов и его реализаций.

Это обычно выражено Big Onownation . В основном вы выбираете простую функцию (как N ² , где n - количество элементов), которые доминируют на фактическом количестве итераций.

location автоматически расширяет путь с помощью basedir проекта. Итак, я думаю, что значение дает вам лучший контроль:

<property name="base.dir" value="/home/myuser"/>

и

<property name="somedir.dir" value="${base.dir}/some_dir"/>

Это специальная ссылка (чтобы отличить его от 0), которая ни на что не указывает.

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

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

Предполагая, что скорость (не память) - ваша основная проблема, и предполагает, что вы хотите эмпирического (не теоретического) способа сравнения алгоритмов, я бы предложил вам подготовить несколько наборов данных, отличающихся по размеру с помощью широкой маржи , как 3 порядка. Затем запустите каждый алгоритм к каждому набору данных, таксируйте их и наберите результаты. Форма каждого времени алгоритма Vs. Кривая размера набора данных даст хорошее представление о его производительности Big-O.

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