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

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

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

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

Конечно, есть проблема с этой идеей, если вы посмотрите на нее сама по себе, что если у вас есть время работы в одну секунду, один час или один год, они различаются только постоянными кратными. Год - это примерно 30 миллионов секунд. Итак, если вас не интересуют множители в 30 миллионов, вы не сможете отличить время выполнения в секундах от времени выполнения в году. Как решить эту проблему?

Что ж, есть какое-то странное решение. На самом деле мы не собираемся рассматривать время выполнения наших программ на каком-либо конкретном входе. Мы собираемся рассмотреть так называемое асимптотическое время выполнения. Затем спросите, как время выполнения масштабируется с размером ввода? По мере того, как размер входных данных n становится больше, может ли масштаб выходных данных быть пропорционален n в квадрате? Это экспоненциально по n? Все это разные вещи. И на самом деле они настолько разные, что, пока n достаточно велико, разница между временем выполнения n и временем выполнения n в квадрате будет хуже, чем любое постоянное кратное.

Если у вас есть постоянное число, кратное 1000, 1000n может оказаться довольно плохим с таким большим числом впереди. Но когда n становится большим, оно все равно лучше, чем n в квадрате.

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

И на самом деле, такого рода асимптотическое крупномасштабное поведение - это то, о чем вы действительно заботитесь много времени, потому что вы действительно хотите знать: что происходит, когда я запускаю свою программу с очень большими входными данными?

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

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

Если вместо n это n log n немного медленнее, вы сможете обрабатывать только входные данные размером около 30 миллионов. Если он работает как n в квадрате, все намного хуже. Вы можете обрабатывать только вводы размером около 30 000, прежде чем это займет больше секунды.

Если входные данные имеют размер от 2 до n, это невероятно плохо, вы можете обрабатывать только входные данные размером около 30 за секунду. На ввод размера 50 уже уходит две недели, на ввод размера 100 вы никогда не закончите. И поэтому разница между n и n в квадрате и 2 с n действительно очень, очень значительна. Часто это более значимо, чем эти множители 5 или 100, которые вы видите по другим причинам.

Теперь, чтобы дать вам еще одно представление о том, как ведут себя различные типы сред выполнения, давайте посмотрим на некоторые типичные моменты, которые вы можете увидеть. Существует log n, который намного меньше, чем root n, который намного меньше, чем n, который намного меньше, чем n log n, которое намного меньше n в квадрате, что намного меньше 2 для n. Итак, если мы построим график всего этого, вы увидите, что эти графики как бы отделены друг от друга. Если вы просто посмотрите на них с небольшими входами, может быть, немного сложно определить, какие из них больше, между ними есть небольшие споры. Но если немного расширить график наружу, он станет намного понятнее. От 2 до n начинается примерно после 4-го реального взлета. На самом деле всего 2 к n после этого просто выстреливает и становится 20 или 30, это просто оставляет всех остальных в пыли. N в квадрате имеет довольно значительное преимущество над всеми остальными. N log n и n также довольно хорошо отделены от других.

На этом графике root n и log n кажутся примерно равными друг другу, но если вы продолжите расширяться, если вы позволите n становиться все больше и больше, они будут очень быстро дифференцируются. Квадратный корень из 1 миллиона составляет около 1000. Логарифм из 1 миллиона - это около 20. И поэтому, если вы продолжаете уходить, очень быстро, чем дальше вы продвигаетесь, тем дальше отдаляются эти вещи друг от друга, и это действительно ключевая идея, лежащая в основе своего рода асимптотики. Нас не так сильно заботят константы, мы заботимся о том, что происходит, когда ваши входные данные становятся очень большими, как они масштабируются.