Программирование

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

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

называющемся машиной с произвольным доступом к памяти (Random Access Machine)

или RAM-машиной. Согласно этой модели наш компьютер работает таким образом:
для исполнения любой простой операции (+, *, -, =, if) требуется ровно один временной шаг;
циклы и подпрограммы не считаются простыми операциями, а состоят из нескольких простых операций. Нет смысла считать подпрограмму сортировки одношаговой операцией, т. к. для сортировки 1 000 000 элементов потребуется определенно намного больше времени, чем для сортировки десяти элементов. Время исполнения цикла или подпрограммы зависит от количества итераций или специфического характера подпрограммы;
каждое обращение к памяти занимает один временной шаг. Кроме этого, наш компьютер обладает неограниченным объемом оперативной памяти. Кэш и диск в модели RAM не применяются.

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

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

важной является оценка сложности алгоритма в наихудшем случае!

функций временной сложности, используя для этого асимптотические обозначения ( -большое

и - большое соответственно).

- Неудобно пользоваться

упрощают задачу сравнения эффективности алгоритмов.

множителями, не учитывая их при вычислении функций.
При таком подходе

функции f(n) = 0,001n2 и g(n) = 1000n2 для нас одинаковы, несмотря на то, что значение функции g(n) в миллион раз больше значения функции f(n) для любого n.

быстродействующем компьютере, исполняющем каждую операцию за одну наносекунду (10-9 секунд).

функции-константы

неотсортированный элемент и помещается в конец отсортированной части массива. Процедура

повторяется до тех пор, пока все элементы массива не будут отсортированы.

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

довольно медленно.

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

массива на половины.

Массив разбивается пополам на каждом вызове до тех пор, пока мы не достигнем единицы. Запишем количество элементов в массиве на каждом вызове: 0-я итерация: n 1-я итерация: n / 2 2-я итерация: n / 4 3-я итерация: n / 8 … i-я итерация: n / 2i … последняя итерация: 1

1 = n / 2i
2i = n
i = log(n)

для достаточно большого значения n. Самый простой алгоритм выполняет (n-1)

операцию умножения (aa  …aa). Но можно указать лучший способ решения этой задачи, приняв во внимание, что n = [n/2]+[n/2].

Для вычисления конечного значения будет достаточно O(log n) операций умножения.

за преступления финансового мошенничества
Мораль логарифмического роста функций ясна: уж если

воровать, так миллионы.

Логарифмические функции возникают при решении задач с повторяющимся делением или удваиванием входных данных.