Какой алгоритм быстрее O (N) или O (2N)?

Ответ 1

Определение большого O:

O (f (n)) = {g | существуют N и c > 0 такие, что g (n) c * f (n) для всех n > N}

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

So O (n) = O (2n). Ни один из них не "быстрее", чем другой, с точки зрения асимптотической сложности. Они представляют одинаковые темпы роста, а именно "линейные" темпы роста.

Доказательство:

O (n) - подмножество O (2n): Пусть g - функция из O (n). Тогда найдутся N и c > 0 такие, что g (n) c * n для всех n > N. Таким образом, g (n) (c/2) * 2n для всех n > N. Таким образом, g находится в O (2n).

O (2n) - подмножество O (n): пусть g - функция из O (2n). Тогда найдутся N и c > 0 такие, что g (n) c * 2n для всех n > N. Таким образом, g (n) 2c * n для всех n > N. Таким образом, g находится в O (n).

Обычно, когда люди ссылаются на асимптотическую сложность ( "большой O" ), они относятся к каноническим формам. Например:

• логарифмический: O (log n)
• linear: O (n)
• linearithmic: O (n log n)
• квадратично: O (n ²)
• экспоненциально: O (c ⁿ) для некоторого фиксированного c > 1

(Здесь более полный список: Таблица общих проблем времени)

Итак, обычно вы должны писать O (n), а не O (2n); O (n log n), а не O (3 n log n + 15 n + 5 log n).

Ответ 2

Timothy Shield answer абсолютно корректен, что O (n) и O (2n) относятся к одному и тому же набору функций, и поэтому он не "быстрее", чем другой. Важно отметить, однако, что более быстрый способ не применим здесь.

Статья в Википедии о нотации Big O использует термин "медленнее растущий", где вы могли бы использовать "быстрее", что лучшая практика. Эти алгоритмы определяются тем, как они растут с ростом n.

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

Ответ 3

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

Ответ 4

Это зависит от констант, скрытых асимптотическим обозначением. Например, алгоритм, который принимает шаги 3n + 5, находится в классе O(n). Таким образом, алгоритм принимает шаги 2 + n/1000. Но 2n меньше 3n + 5 и больше, чем 2 + n/1000...

Это немного похоже на вопрос, если 5 меньше некоторого неуказанного числа от 1 до 10. Это зависит от неуказанного числа. Просто зная, что алгоритм, выполняемый в шагах O(n), недостаточно информации, чтобы решить, будет ли алгоритм, выполняющий шаги 2n, быстрее или быстрее.

На самом деле это еще хуже: вы спрашиваете, превышает ли какой-то неуказанный номер от 1 до 10, чем какой-либо другой неуказанный номер между 1 и 10. Наборы, которые вы выбираете из одного и того же, не означают номера, которые вы произойдет выбор будет равен! O(n) и O(2n) являются наборами алгоритмов, и поскольку определение Big-O отменяет мультипликативные факторы, они являются одинаковыми. Отдельные члены наборов могут быть быстрее или медленнее, чем другие члены, но наборы одинаковы.