Что означает более быстрый алгоритм в теоретической информатике?

Если существует алгоритм, работающий во времени $O(f(n))$ для некоторой задачи A, и кто-то придумывает алгоритм, работающий во времени, $O(f(n)/g(n))$ , где $g(n) = o(f(n))$ , считается ли это улучшением по сравнению с предыдущим алгоритмом?

Имеет ли смысл в контексте теоретической информатики придумать такой алгоритм?

Нет, алгоритм, работающий во времени , где g ( n ) = o ( f ( n ) ) , не обязательно считается улучшением. Например, предположим, что f ( n ) = n и g ( n ) = 1 / n . Тогда O ( f ( n ) / g $O(f(n)/g(n))$$g(n) = o(f(n))$$f(n) = n$$g(n) = 1/n$ является худшей временной границей, чем O ( f ( n ) ) = O ( n ) .$O(f(n)/g(n)) = O(n^2)$$O(f(n)) = O(n)$

Чтобы улучшить алгоритм, работающий во времени , вам нужно придумать алгоритм, работающий во времени o ( f ( n ) ) , то есть во времени g ( n ) для некоторой функции g ( n ) = o ( f ( n ) $f(n)$$o(f(n))$$g(n)$$g(n) = o(f(n))$ .

Если все, что вам известно, это то, что алгоритм работает за время , то неясно, является ли алгоритм, работающий за время O ( g ( n ) ), улучшением, независимо от того, f ( n ) , g ( n) ) являются Это потому, что большой O является только верхней границей времени выполнения. Вместо этого, общепринято рассматривать временную сложность в худшем случае, и оценить его как большое & thetas , а не просто как большой O .$O(f(n))$$O(g(n))$$f(n),g(n)$$\Theta$$O$

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

Предположим, у вас есть алгоритм , фактическое время выполнения которого составляет 1 n 2 + 2 n + 1 (при условии, что вы действительно можете посчитать инструкции и узнать точные значения времени и т. Д., Что по общему признанию является огромным допущением в современных системах). Затем предположим, что вы придумали новый алгоритм, который оказывается O ( n ) , но фактическое время выполнения составляет 1000 n + 5000 . Также предположим, что вы знаете, что программное обеспечение для использования этого алгоритма никогда не увидит проблему размером n > 10 .$O(n^2)$$1n^2+2n+1$$O(n)$$1000n + 5000$$n>10$

Итак, что бы вы выбрали - алгоритм , который займет 15000 единиц времени, или алгоритм O ( n 2 ), который займет всего 121 единицу? Теперь, если ваше программное обеспечение развивается для обработки проблемных размеров n > 100000 , какой из них вы бы выбрали? Что бы вы сделали, если размер вашей проблемы сильно варьируется?$O(n)$$O(n^2)$$n>100000$

Как правило, это означает, что для любого размера ввода, который достаточно велик, наихудшее время работы старого алгоритма медленнее, чем нового. Это эквивалентно формализму , где g - временная сложность нового алгоритма, а f - временная сложность старого.$g(n) \in o\bigl(f\left(n\right)\bigr)$$g$$f$

Иногда, однако, компьютерные ученые заботятся о средней производительности. Классическим примером является Quicksort: его наихудший среда является , тогда как мы знаем , другие , которые работают в thetas ; ( п авторизуйтесь п ) время, но он широко используется на практике из - за его хорошей среднем случае время работает. Кроме того, его можно настроить так, чтобы он работал очень быстро в случаях, наиболее часто встречающихся в условиях дикой природы, таких как массивы, которые в основном находятся в правильном порядке.$\Theta(n^2)$$\Theta(n \log n)$

И иногда даже теоретики-компьютерщики используют «быстрее» так же, как обычные люди. Например, большинство реализаций классов String имеют оптимизацию Short String (также называемую Small String Optimization), даже если она ускоряет работу только для коротких строк и является чисто служебной информацией для более длинных. По мере того как размер входных данных становится все больше и больше, время выполнения операции String с SSO будет увеличиваться на небольшой постоянный член, поэтому по определению, которое я дал в первом абзаце, удаление SSO из класса String делает его «быстрее На практике, тем не менее, большинство строк маленькие, поэтому SSO позволяет большинству программ использовать их быстрее, и большинство профессоров в области компьютерных наук знают лучше, чем ходя вокруг, требуя, чтобы люди говорили только о порядках асимптотической сложности времени.

Нет единого определения того, что такое «более быстрый алгоритм». Не существует руководящего органа, который решает, является ли алгоритм более быстрым, чем другой.

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

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

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

Pick up the jar
Grab the lid
Unscrew the lid

Против

Pick up the jar
Put the jar back down
Pick up the jar
Put the jar back down
Pick up the jar
Put the jar back down
Pick up the jar
Put the jar back down
Pick up the jar
Put the jar back down
Pick up the jar
Grab the lid
Unscrew the lid

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

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

Таким образом, в одном случае мы можем изменить O (n) на O (n) и вызвать его быстрее. При других обстоятельствах мы можем изменить O (2 ^ n) на O (2 ^ n / n ^ 100) и утверждать, что никакого существенного ускорения не было вообще. Вот почему я говорю, что нет единого определения для «более быстрого алгоритма». Это всегда зависит от контекста.

$A(n) \in O(f(n))$

$$\exists \ 0 \le c_f \lt \infty \mid \ \limsup_{n \to \infty} \frac{A(n)}{f(n)} = c_f$$

Now, let us assume we are talking about an arbitrarily increasing function $g(n)$ where $\limsup_{n\to\infty} g(n) = \infty$ and let us create the function $h(n) = \frac{f(n)}{g(n)}$.

We are given that the run-time of the "improved" algorithm $A'(n)$ is in $O(h(n))$. Suppose that the run-time of the original algorithm $A(n)$ is also in $O(h(n))$. This can be written as follows.

$$\exists \ 0 \le c_h \lt \infty \mid \ \limsup_{n \to \infty} \frac{A(n)}{h(n)} = c_h$$

Using the rules of limits, we can also write:

$$c_h = \limsup_{n \to \infty} \frac{A(n)}{h(n)} = \limsup_{n \to \infty} \frac{A(n)g(n)}{f(n)} = c_f \cdot \limsup_{n \to \infty} g(n)$$

Since $c_h \lt \infty$, this can only be true if $c_f = 0$.

The contrapositive statement is: If $c_f \neq 0$, then $A(n) \notin O(h(n))$.

In words, $A'(n)$ is an "improvement" on $A(n)$ under the additional conditions that $A(n) \in \Theta(f(n))$ and $g(n)$ is arbitrarily increasing.

Additionally, this should show why the statement that $A(n) \in O(f(n))$ is not strong enough to draw a conclusion about whether $A'(n)$ is an "improvement." In short, $A(n)$ could already be in $O(h(n))$.