Почему алгоритмы O (n ^ 2) становятся более неэффективными, чем больше элементов они сортируют?

Question

Кто-нибудь может дать четкое определение того, ПОЧЕМУ O (n ^ 2) алгоритмы становятся все более и более неэффективными, чем больше количество элементов, которые они должны отсортировать?

Например, пузырьковая сортировка - 4096 элементов занимает 24,56мс для сортировки, где 8192 элемента занимают 98,56 мс для сортировки.Может ли кто-нибудь четко объяснить , почему рост такой?

Answer 1

это означает, что функция O (n ^ 2).

, что для n элементов ваш алгоритм будет примерно таким же, как O (n ^ 2).

(8192 ^ 2) / (4096 ^ 2) = 4, то есть 2 ^ 2 роста

и 98,56 / 24,56 = 4,013 ..

Answer 2

O (n²) означает, среди прочего, что соотношение между временем, необходимым для сортировки элементов X, и временем, необходимым для сортировки элементов Y, составляет приблизительно X² / Y² (приближаясь к этому, когда X и Y приближаются к бесконечности).

Давайте посчитаем:

8192² / 4096² = 2² = 4.00
98.56 / 24.56      ≈ 4.01

Действительно, ваш тип O (n²), и это то, что вы должны ожидать.

Answer 3

Строго говоря, Big-O не говорит о росте числа, которое вы фактически используете.

Запись Big-O - это то, что происходит в пределе как размерпроблема (n) стремится к бесконечности.Конкретные небольшие числа, такие как 4096 и 8192, не имеют отношения к классификации Big-O.Кроме того, big-O - это верхний предел .Пузырьковая сортировка O (n ^ 2).Это также O (n ^ 3), и O (n ^ 27), и O (2 ^ n), потому что все эти функции также обеспечивают верхние границы своего времени работы в пределе.Очень слабые верхние границы, но, тем не менее, границы.

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

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

Итак, когда кто-то говорит вам, чтоАлгоритм O (n ^ 2), есть довольно высокая вероятность того, что они пытаются сказать вам, что его худший случай Θ (n ^ 2), и если это так, они вполне могут быть дальшепытаюсь сказать вам, что эта тенденция наблюдается для тех видов n, которые вам небезразличны.Учитывая это злоупотребление обозначениями, поэтому «O (n ^ 2) алгоритмы» все становятся менее эффективными, когда вы увеличиваете n.

Answer 4

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

Это означает, что если вы удвоите размер входа,алгоритм будет работать примерно в 4 раза дольше.Это соответствует времени, которое вы испытываете.

Answer 5

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

Я бы посоветовал вам взглянуть на Википедию и прочитать о Big O нотации и Алгоритмы сортировки ; статьи действительно читабельны.

Что касается самой нотации, O (n2) может быть быстрее, чем алгоритм O (n logn) для определенных наборов данных и размеров, это зависит от констант. И даже если не быстрее, потребление памяти может быть фактором при сортировке огромных наборов данных.

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

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

Answer 6

O означает, что верхняя граница, то есть рост функции, не будет превышать рост функции, которая определена внутри O ().f(x) = O (g(x)) означает |f(x)| <= C|g(x)| для некоторых x > k и для некоторой константы C (которые называются свидетелями).Означает, что для некоторых C и k, если мы построим функции, тогда для всех точек x > k g (x) будет всегда больше для каждого x> k, то есть g(x) определяет верхнюю границу.Обратите внимание, что функция g(x) может иметь более низкие значения, чем f(x) для x<k.

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

Answer 7

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

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

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

Другой пример O (n ^ 2): скажем, у вас есть n точек, и для каждого из них вы должны найти ближайшего соседа.Если n = 10, вам придется сделать 9 сравнений для каждой точки => 9 * 10 = 90 сравнений.Если вы удвоите размер, n = 20, вам придется сделать 19 сравнений пр.точка.Поэтому алгоритм становится «менее эффективным» для каждой точки.=> 19 * 20 = 380 сравнений примерно в 2 ^ 2 = 4 раза больше.

Answer 8

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

Answer 9

Все зависит от данных.Для пузырьковой сортировки O (n ^ 2) - наихудший сценарий.Это может быть так же хорошо, как O (n), если вы сортируете уже отсортированный список.

Генерация O () означает наихудший сценарий для данного алгоритма.