Интерпретировать результаты алгоритма эксперимента?

Question

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

Array size --- number of operations

10000 --- 238393

20000 --- 511260

40000 --- 1120512

80000 --- 2370145

Edit:

Я удалил неправильный вопрос, который задавал в этом сообщении. То, что я на самом деле спрашиваю, -

Что я пытаюсь выяснить, так это «складываются ли эти результаты с теоретической сложностью быстрой сортировки (O (N * log (N)))»?

Answer 1

Теперь, по сути, мне нужно знать, как мне интерпретировать эти результаты, чтобы я мог определить сложность быстрой сортировки Big Oh?

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

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

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

РЕДАКТИРОВАТЬ:

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

Answer 2

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

Вы можете сделать это с помощью графика некоторых функций y = f(n), таких как f(10000) ~= g(10000) [где g ваша функция], и проверить разницу в поведении.

В вашем примере мы получаем следующие графики:

Мы ясно видим, что:

1. Поведение ваших результатов суб-квадрик
2. Поведение выше линейного.
3. Это очень близко к логарифмическому поведению, но только немного "выше".

Из этого мы можем сделать вывод, что ваши алгоритмы , вероятно, O(n^2) [не строго! помните, большой O не является строгой границей], и также может быть O(nlogn), если мы выводим, что отличие от функции O(nlogn) является шумом.

Примечания:

1. Этот метод ничего не доказывает об алгоритме, и особенно не дает вам худшего случая [или даже среднего случая].
2. Этот метод обычно используется для оценки двух алгоритмов , а не некоторых предварительно определенных функций, чтобы проверить, какой из них лучше для каких входов.

EDIT:
Я нарисовал все графики как y1(x) = f(x), y2(x) = g(x), ... потому что мне было проще объяснить этот способ, но обычно, когда вы сравниваете два алгоритма [как вы часто используете этот метод], функция y(x) = f(x) / g(x), а вы проверяете, остается ли y(x) близким к 1, растет, уменьшается?