Python: введение в алгоритмический анализ

предисловие

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

1. Зачем проводить алгоритмический анализ?

Предположим, что есть два алгоритма для решения одной и той же задачи, и время, затрачиваемое алгоритмом 1, равно T_1(N)=100N , время, затраченное на алгоритм 2, равно T_2(N)=N^2 . впредставляет собой количество данных, которые необходимо обработать для решения задачи, когдаКогда они равны, судить о том, какой алгоритм быстрее, зависит отразмер или объем данных, подлежащих обработке. Когда объем данных мал, алгоритм 1 занимает больше времени, чем алгоритм 2; когдаПосле некоторого критического значения (здесь 100) время, затрачиваемое Алгоритмом 2, резко возрастает, намного превосходя Алгоритм 1, в то время как Алгоритм 1 увеличивается относительно медленно.

Видно, что, просто глядя на фактическое время работы алгоритма даже в одной среде, мы не можем получить непротиворечивый ответ на вопрос, какой алгоритм лучше. Чтобы обеспечить единый критерий для алгоритма, нам нужен более общий метод анализа.

2. Четыре основных математических определения

Я полагаю, что многие читатели начинают паниковать, когда видят слово «математика», и еще более невыносимо, что их сразу четыре. Но не паникуйте, хотя математическое определение выглядит жестким и негибким, фактический смысл можно объяснить одним предложением. Конечно, мы не можем винить математиков, которые определяют его ради строгости. Здесь, кроме первого крупногоОпределение, три других определения, чтобы иметь возможность более четко видеть разницу между определениями, автор скорректировал формат символов и порядок языка, исходя из того же значения. Тщательное сравнение найти не сложно, на самом деле нам нужно понять только первый большойПо определению, другие на самом деле говорят о разных случаях одного и того же.

2.1 Большойопределение

если есть нормальныйи n_0 , так что когда N >= n_0 час, T(N)<=cf(N) , затем обозначается как T(N)=O(f(N)) .

2.2 Большой $\Omega$ определение

если есть нормальныйи n_0 , так что когда N >= n_0 час, T(N)>=cf(N) , затем обозначается как $T(N)=\Omega(f(N))$ .

2,3 большой $\Theta$ определение

когда T(N)=O(f(N)) и $T(N)=\Omega(f(N))$ , записывается как $T(N)=\Theta(f(N))$ .

2,4 маленькийопределение

когда T(N)=O(f(N)) и $T(N) \neq \Omega(f(N))$ , записывается как.

2.5 Скажи что-нибудь человеческое

Прочитав четыре определения, поместите их в конкретные сценарии. Например, T(N） Представляет время выполнения алгоритма в разделе 1, а N по-прежнему относится к объему данных, обработанных алгоритмом. Когда объем данных очень велик,Представляет собой верхний предел времени работы алгоритма, максимальное $\Omega$ нижний предел, большой $\Theta$ Это означает, что временная сложность обоих алгоритмов одинакова, чем меньшес большимОтличие в том, что маленькийне может быть равно верхнему пределу, а большеМожет.

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

3. Используйте большиеАнализ временной сложности алгоритма

Мы уже знаем большоезаключается в том, чтобы определить ограничение по времени (функцию) для алгоритма f(N) , пока время работы алгоритма не превышает этого верхнего предела, можно сказать, что временная сложность алгоритма равна T(N) = O(f(N)) . Поэтому используйте большоеСуть анализа временной сложности алгоритма состоит в том, чтобы дать функцию верхней границы для оценки времени работы алгоритма. Конечно, математически существует более одной такой функции верхней границы. Чтобы упростить анализ, мы примем следующее соглашение: конкретной единицы времени не существует. Поэтому при анализе мы отбросим常数系数и低阶项,покидать常数系数и低阶项, покидать常数系数и低阶项. Важные вещи говорятся трижды.

3.1 Возьми каштан

рассчитать $\sum_{i=1}^{n} i^3$

def Sum(N):
    sum = 0                     # 1
    for i in range(1, N+1):     # 2
        sum += i * i *i         # 3
    return sum                  # 4

Анализировать эту программу просто. Каждая из строк метки 1 и 4 занимает одну единицу времени; строка 3 выполняет четыре единицы времени (2 умножения1 дополнение1 задание) и выполнитьобщая занятостьединицы времени; строка 2 инициализируетiЗаймите единицу времени, проверьтеi <= NЗанять N+1 единицы времени и все операции автоинкрементаединиц времени, всего 2N+2 . Игнорируя накладные расходы на вызов функции и возврат значения, результирующая сумма равна 6N+4 . Отбросить постоянные коэффициенты6и условия более низкого порядка4(можно рассматривать как 4N^0 ), мы говорим, что временная сложность этой функции равна O(N) .

Если вы считаете, что такой способ анализа кода построчно слишком громоздкий. Хорошая новость заключается в том, что нам не нужно каждый раз прибегать к такому неуклюжему подходу. На самом деле анализ показывает, что, можно обнаружить, что точная количественная оценка единиц времени во многих местах не нужна или даже избыточна, потому что именно эти точные значения мы и хотим в итоге отбросить常数系数и低阶项. Таким образом, мы получаем несколько общих правил.

3.2 Общие правила

3.2.1 Правило 1 — Циклы FOR

однаждыforВремя работы цикла не болееforВремя выполнения операторов внутри цикла (включая тесты) умножается на количество итераций.

То есть, еслиNдаforКоличество итераций цикла, тогда его временная сложность равна O(N) . Например:

for i in range(N):
    count += 1

3.2.2 Правило 2. Вложенные циклы FOR

Проанализируйте эти петли изнутри. Общее время выполнения оператора внутри набора вложенных циклов равно времени выполнения оператора, умноженному на всеforПроизведение размера петли.

Например, временная сложность следующего фрагмента программы равна O(N^2) :

for i in range(N):
    for j in range(N):
        k += 1

3.2.3 Правило 3 - Последовательные заявления

Суммируйте время работы отдельных операторов, максимальный срок (отбросьте低阶项) — результирующее время работы.

Например, в следующем фрагменте программы сначала используется O(N) , то потратьте O(N^2) , общая стоимость также O(N^2) .

for i in range(N):
    count += 1

for i in range(N):
    for j in range(N):
        k += 1

3.2.4 Правило 4. Операторы IF/ELSE

Для фрагментов программы

if condition:
    statement_block1
else:
    statement_block2

Одинif/elseУтверждения никогда не занимают больше времени, чем суждение плюс блок утверждений.statement_block1иstatement_block2Общее прошедшее время старшего. Очевидно, что в некоторых случаях это завышенная оценка, но ни в коем случае не заниженная.

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

def Factorial(N):
    if N <= 1:                      # O(1)
        return 1                    # O(1)
    else:
        return N * Factorial(N - 1) # O(N)

Найдите факториальную функциюFactorialв, судьяN <= 1за O(1) ,ifБлок операторов ветвления O(1) ,elseБлок оператора ветвления является рекурсивным вызовом, но по сложности эквивалентенforпетля, так O(N) , поэтому временная сложность всего фрагмента программы равна O(N) .

Эпилог

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

Thank u

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

Отсканируйте QR-код в WeChat, чтобы получить ценные технические оригиналы