Я только что доказал, что сито Эратосфена менее эффективно, чем пробное деление?

TL; DR: бессмысленно сравнивать скорость вариантов кода при одном размере ввода; сравнение эмпирических порядков роста действительно отражает алгоритмическую природу кода и будет согласованным на разных тестовых платформах для одного и того же тестового диапазона входных размеров. Сравнение абсолютных значений скорости имеет смысл только для вариантов кода, которые демонстрируют такое же асимптотическое или, по крайней мере, локальное поведение роста.

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

Таким образом, даже если на некотором вводе code_1 работает в 10 раз быстрее, чем code_2, но его время выполнения удваивается с каждым удвоением размера ввода, тогда как для code_2 оно увеличивается только как 1.1x, очень скоро code_2 станет намного быстрее, чем code_1.

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

В частности, теоретическая сложность пробного деления составляет O(n^1.5 / (log n)^0.5) в n простых числах, обычно рассматриваемых как ~ n^1.40..1.45 эмпирический порядок роста (но изначально он может быть ~n^1.3 для меньших размеров входных данных). Для сита Эратосфена это O(n log n log (log n)), обычно обозначаемый ~ n^1.1..1.2. Но, безусловно, существуют неоптимальные реализации как пробного деления, так и сита Эратосфена, которые работают на ~n^2.0 и хуже.

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

Прогноз с известной достоверностью - это то, что научный метод это все о.

Нет, затраченное время выполнения не является стандартом для измерения эффективности, поскольку оно варьируется от платформы к платформе - утверждение «мой алгоритм работал за 10 секунд» практически не дает информации о самом алгоритме. В дополнение к этому вам нужно будет перечислить все спецификации среды и другие процессы, запущенные одновременно, и это будет огромным беспорядком. Отсюда и развитие порядковых обозначений (Big Oh, Little Oh, Omega и т. Д.).

Эффективность обычно подразделяется на два подраздела:

1. Эффективность времени.
2. Эффективность использования пространства.

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

Обратите внимание: я прикрепляю ссылку для обозначения Big Oh - все родственные обозначения можно найти на этой странице Википедии, и обычно это хорошее место для начала. Это также затронет разницу в пространственной и временной эффективности.

Небольшое применение эффективности времени с помощью Big Oh:

Рассмотрим следующую рекурсивную функцию в Racket (была бы в Python, если бы я знал это - лучший псевдокод, который я могу сделать):

(define (fn_a input_a)
  (cond
    [(empty? input_a) empty]
    [(empty? (rest input_a)) input_a]
    [(> (first input_a) (fn_a (rest input_a))) (cons (first input_a) empty)]
    [else (fn_a (rest input_a))]))

... мы видим, что: empty?, rest, > и first - все O (1). Мы также замечаем, что в худшем случае выполняется вызов fn_a в третьем условии и четвертом условии для rest из input_a. Тогда мы можем записать наше рекуррентное соотношение как T (n) = O (1) + 2T (n - 1). Глядя на это на диаграмме рекуррентных отношений, мы видим, что fn_a имеет порядок O (2 ^ n), потому что в худшем случае выполняются два рекурсивных вызова.

Также важно отметить, что по формальному определению Big Oh также правильно (хотя и бесполезно) утверждать, что fn_a равно O (3 ^ n). Многие алгоритмы при анализе указываются с использованием Big Oh, однако было бы более целесообразно использовать Big Theta для ужесточения границ, что по сути означает: самый низкий, наиболее точный порядок по отношению к данному алгоритму.

Будьте осторожны, прочтите официальные определения!

Означает ли более длительное время выполнения менее эффективный алгоритм?

Не обязательно. Эффективность программы измеряется не только затраченным временем, но и затрачиваемыми ресурсами. Пространство - еще один фактор, о котором следует помнить при рассмотрении эффективности.

Из wiki: -

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

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

Выполняет каждый тест много раз и использует некоторую статистику по результатам (например, среднее значение или среднее значение / отклонение в зависимости от того, насколько вы заботитесь)

И / или заставить его выполнять больше работы - например, находить большее количество простых чисел.

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

Будьте осторожны при измерениях - убедитесь, что ваши инструменты для измерения времени точны.

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

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

В качестве альтернативы в одной из ваших реализаций может быть большой

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