Чтение этой статьи поможет вам ответить на следующие вопросы: Что такое алгоритм? Алгоритм сложный? Как мы можем ознакомиться с классическими алгоритмами в отрасли за короткий промежуток времени? Как будут выглядеть эти алгоритмы при реализации на Python? Будет ли их потребление времени связано с временной сложностью?
Бог это алгоритм?
Инструкции в алгоритме описывают вычисление, которое при запуске может начинаться с начального состояния и (возможно, пустого) начального ввода, проходить через конечный и четко определенный ряд состояний, в конечном итоге производить вывод и останавливаться в конечном состоянии. Переход из одного состояния в другое не обязательно детерминирован. Некоторые алгоритмы, включая алгоритмы рандомизации, содержат некоторые случайные входные данные.
Несколько характеристик алгоритма
Алгоритм должен обладать такими важными характеристиками, как «конечность», «точность», «входные данные», «выходные данные», «выполнимость» и так далее. Соответствующие значения этих признаков следующие:
- Конечность. Конечность алгоритма означает, что алгоритм должен иметь возможность завершаться после выполнения конечного числа шагов;
- Определенность — каждый шаг алгоритма должен иметь точное определение;
- Вход - Алгоритм имеет 0 или более входов для описания начального условия операнда.Так называемый вход 0 означает, что сам алгоритм определяет начальные условия;
- Выход. Алгоритм имеет один или несколько выходов, отражающих результаты обработки входных данных. Алгоритмы без выходных данных бессмысленны;
- Эффективность. Любой вычислительный шаг, выполняемый в алгоритме, может быть разложен на основные выполняемые шаги, то есть каждый вычислительный шаг может быть завершен за конечное время (также известное как эффективность).
Два элемента алгоритма
-
Во-первых, операции и операции с объектами данных: основные операции, которые может выполнять компьютер, описываются в виде инструкций. Совокупность всех инструкций, которые может выполнить компьютерная система, становится системой инструкций компьютерной системы. Основные операции и операции компьютера делятся на следующие четыре категории:
- 1 Арифметические операции: такие операции, как сложение, вычитание, умножение и деление
- 2 Логические операции: или, и, не равные операции
- 3 Операции отношения: больше, меньше, равно, не равно и т. д.
- Передача данных 4: вход, вывод, и поэтому оператор назначения [1]
-
Во-вторых, управляющая структура алгоритма: функциональная структура алгоритма зависит не только от выбранных операций, но и от порядка выполнения между операциями.
Оценка качества алгоритма
Вы говорите, что алгоритм хороший, а он говорит, что алгоритм плохой, и они бесконечно спорят. Так как же нам судить, хорошо это или плохо?
Одна и та же задача может быть решена с помощью разных алгоритмов, и качество алгоритма будет влиять на эффективность алгоритма и даже программы. Цель анализа алгоритма состоит в том, чтобы выбрать подходящий алгоритм и улучшить алгоритм. Оценка алгоритма в основном рассматривается с точки зрения временной сложности и пространственной сложности.
- Временная сложность. Временная сложность алгоритма относится к объему вычислительных усилий, необходимых для выполнения алгоритма. В общем случае компьютерный алгоритм представляет собой функцию f(n) от размера задачи n, поэтому обозначается временная сложность алгоритма. Т (п) = О (ф (п)) Следовательно, чем больше размер задачи n, тем больше скорость роста времени выполнения алгоритма, тем больше скорость роста f(n), что называется асимптотической временной сложностью.
- Пространственная сложность. Пространственная сложность алгоритма относится к пространству памяти, которое алгоритм должен потреблять. Его метод расчета и представления аналогичен временной сложности, которая обычно представлена асимптотикой сложности. По сравнению с временной сложностью анализ пространственной сложности намного проще.
- Корректность - корректность алгоритма представляет собой алгоритм оценки плюсов и минусов наиболее важных критериев.
- Удобочитаемость. Удобочитаемость алгоритма относится к тому, насколько легко алгоритм может быть прочитан людьми.
- Надежность. Надежность относится к способности алгоритма реагировать и обрабатывать необоснованный ввод данных, также известной как отказоустойчивость.
Приведенные выше теоретические знания могут дать нам общее понимание и понимание алгоритма.Далее мы будем использовать Python для реализации нескольких классическихАлгоритм сортировкии сравните реализацию Java в конце статьи.
Внутри и снаружи алгоритма
В дополнение к ученикам «Секты Тан» (Секта Тан на континенте Доуло) алгоритм сортировки также имеет внутренние и внешние точки.
- Внутренняя сортировка относится к сортировке в памяти;
- Внешняя сортировка относится к ситуации, когда во время процесса сортировки необходимо получить доступ к внешнему хранилищу из-за большого объема данных, которые невозможно прочитать в память;
Более классический алгоритм сортировки показан на следующем рисунке:
Существуют пузырьковая сортировка, сортировка слиянием, сортировка вставками, сортировка по холму, сортировка выбором, быстрая сортировка и т. д.
Их соответствующие временные сложности показаны на следующем рисунке:
Примечание. Сегодня мы поговорим о всплытии, выборе и сортировке вставками.
Прежде чем начать, я хотел бы поблагодарить большого парня «Программист Сяо Ву» официального аккаунта «Обучение алгоритмам за пять минут» за авторизацию динамических картинок и сортировку идей.
Пузырьковая сортировка
Процесс пузырьковой сортировки показан на рисунке выше, а соответствующие шаги алгоритма:
Судя по динамическому графику и шагам алгоритма, код реализации пузырьковой сортировки в Python выглядит следующим образом:
data = [5, 4, 8, 3, 2]
def bubble(data):
for i in range(len(data)-1): # 排序次数
for s in range(len(data)-i-1): # s为列表下标
if data[s] > data[s+1]:
data[s], data[s+1] = data[s+1], data[s]
return data
print(bubble(data))
После запуска программы вывод:
[2, 3, 4, 5, 8]
Это метод с высокой временной сложностью, и время его сортировки увеличивается с увеличением длины списка.
сортировка выбором
Процесс и шаги сортировки выбором показаны на рисунке выше.Согласно динамической диаграмме и шагам алгоритма, код реализации сортировки выбором в Python выглядит следующим образом:
data = [3, 4, 1, 6, 2, 9, 7, 0, 8, 5]
def selections(nums):
for i in range(len(nums)):
min_index = min(nums) # 最小值
for j in range(len(nums) - i):
if nums[min_index] < nums[j]:
min_index = j
nums[min_index], nums[len(nums) - i - 1] = nums[len(nums) - i - 1], nums[min_index]
return nums
print(selections(data))
Метод min() может получить минимальное значение в списке, и текущий результат:
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
Так как min() имеет эту функцию (примечание: метод max() может получить максимальное значение в списке), мы можем использовать его.Код, который немного сложнее:
data = [3, 4, 1, 6, 2, 9, 7, 0, 8, 5]
res = []
for i in range(0, len(data)):
aps = min(data)
data.remove(aps)
res.append(aps)
print(res)
Результат, полученный после запуска:
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
Если вы замените метод min() на метод max(), результат вывода будет следующим:
[9, 8, 7, 6, 5, 4, 3, 2, 1, 0]
Можно ли назвать такое поведение выбора только самого большого или самого маленького элемента списка выборочной сортировкой?
Хотя код, написанный таким образом, короче и понятнее. Но какова его временная сложность?
Во-первых, подтвердите временную сложность мин. и макс. Кто-то дал временную сложность каждой операции со списком:
Видно, что и min, и max растут с длиной списка, а сам цикл for требуется один раз, поэтому временная сложность этого метода записи составляет
Это действительно так?
В коде есть операция удаления, которая удаляет элементы исходного списка, но временная сложность удаления также равна O(n), не становится ли это O(n*n + n), как решить эту проблему .
Замечено, что временная сложность pop равна O(1), поэтому можно ли использовать pop для уменьшения временной сложности? list предоставляет метод для получения нижнего индекса элемента, мы пытаемся изменить код на:
data = [3, 4, 1, 6, 2, 9, 7, 0, 8, 5]
res = []
for i in range(0, len(data)):
aps = max(data)
result = data.pop(data.index(aps))
print(result)
res.append(aps)
print(res)
Результат, полученный после запуска:
9
8
7
6
5
4
3
2
1
0
[9, 8, 7, 6, 5, 4, 3, 2, 1, 0]
Видно, что действительно можно удалять элементы списка по индексу, и сложность удаления элементов снижается.
Держись, момент сложности вышеуказанного поп есть O (1), но как насчет времени сложности POP (Data.index (I))? Это также o (1)? Мы можем сделать эксперимент для проверки:
# 崔庆才丨静觅、韦世东丨奎因 邀请你关注微信公众号【进击的Coder】
from datetime import datetime
data = [i for i in range(500000)]
start_time = datetime.now()
for i in range(len(data)):
data.pop(data.index(i))
print(data)
print(datetime.now() - start_time)
Это код pop(data.index(i)), и результат выглядит следующим образом:
[]
0:00:40.151812
тогда как если вы используете pop()
from datetime import datetime
data = [i for i in range(500000)]
start_time = datetime.now()
for i in range(len(data)):
data.pop()
print(data)
print(datetime.now() - start_time)
Результат после запуска:
[]
0:00:00.071441
Результат очевиден, временная сложность pop(i) по-прежнему связана с количеством элементов, а не с ожидаемым O(1). Поскольку элементы списка продолжают уменьшаться, его временная сложность не равна O(n).Если предположить, что текущее количество элементов списка равно k, то временная сложность этой части равна O(k). Это показывает, что короткий метод записи минимум-максимум может в определенной степени уменьшить временную сложность.
Убедитесь, что запись двух циклов for и краткая запись mix max занимают много времени:
from datetime import datetime
data = [i for i in range(30000)]
def selections(nums):
for i in range(len(nums)):
min_index = min(nums) # 最小值
for j in range(len(nums) - i):
if nums[min_index] < nums[j]:
min_index = j
nums[min_index], nums[len(nums) - i - 1] = nums[len(nums) - i - 1], nums[min_index]
return nums
start_time = datetime.now()
selections(data)
print(datetime.now() - start_time)
Взяв в качестве примера 30 000 элементов, время выполнения двух циклов for составляет около 47 секунд. И тот же номер, отсортированный по min max:
from datetime import datetime
data = [i for i in range(30000)]
start_time = datetime.now()
res = []
for i in range(0, len(data)):
aps = max(data)
# del data[data.index(aps)]
data.pop(data.index(aps))
res.append(aps)
print(datetime.now() - start_time)
Затраченное время — 12 секунд, такой же результат получается с методами del и pop в коде.
Тоже... есть такая операция?
Сортировка выбором также является методом с относительно высоким верхним пределом временной сложности, и время его сортировки также увеличивается с увеличением длины списка.
Сортировка вставками
Процесс и этапы сортировки вставками показаны на рисунке выше.Согласно динамической диаграмме и шагам алгоритма, код реализации сортировки вставками в Python выглядит следующим образом:
from datetime import datetime
data = [i for i in range(30000)]
data.insert(60, 5)
# 崔庆才丨静觅、韦世东丨奎因 邀请你关注微信公众号【进击的Coder】
def direct_insert(nums):
for i in range(1, len(nums)):
temp = nums[i] # temp变量指向尚未排好序元素（从第二个开始）
j = i-1 # j指向前一个元素的下标
while j >= 0 and temp < nums[j]:
# temp与前一个元素比较，若temp较小则前一元素后移，j自减，继续比较
nums[j+1] = nums[j]
j = j-1
nums[j+1] = temp # temp所指向元素的最终位置
return nums
start_time = datetime.now()
res = direct_insert(data)
print(datetime.now() - start_time)
print(len(res), res[:10])
После создания списка вставьте элемент со значением 5 в столбец с индексом 60, и объем данных теперь равен 30 001. Результат запуска кода:
0:00:00.007398
30001 [0, 1, 2, 3, 4, 5, 5, 6, 7, 8]
Вы можете видеть, что сортировка списка из 30 100 элементов занимает очень мало времени, а при разрезании вы видите, что порядок уже отсортирован.
Затем выберите тестовый код выглядит следующим образом:
from datetime import datetime
data = [i for i in range(30000)]
data.insert(60, 5)
def selections(nums):
for i in range(len(nums)):
min_index = min(nums) # 最小值
for j in range(len(nums) - i):
if nums[min_index] < nums[j]:
min_index = j
nums[min_index], nums[len(nums) - i - 1] = nums[len(nums) - i - 1], nums[min_index]
return nums
start_time = datetime.now()
res = selections(data)
print(datetime.now() - start_time)
print(len(res), res[:10])
Вывод после запуска кода:
0:00:47.895237
30001 [0, 1, 2, 3, 4, 5, 5, 6, 7, 8]
Видно, что сортировка списка из 30 010 элементов не короткая, заняла 47 секунд, а по нарезке видно, что порядок выстроен.
Затем попробуйте сортировку выбора типа max min, и результат будет следующим:
0:00:14.150992
30001 [29999, 29998, 29997, 29996, 29995, 29994, 29993, 29992, 29991, 29990]
Это просто, почему эта операция экономит столько времени?
Наконец проверьте пузырение:
# 崔庆才丨静觅、韦世东丨奎因 邀请你关注微信公众号【进击的Coder】
from datetime import datetime
data = [i for i in range(30000)]
data.insert(60, 5)
def bubble(data):
for i in range(len(data)-1): # 排序次数
for s in range(len(data)-i-1): # s为列表下标
if data[s] > data[s+1]:
data[s], data[s+1] = data[s+1], data[s]
return data
start_time = datetime.now()
res = bubble(data)
print(datetime.now() - start_time)
print(len(res), res[:10])
Вывод после запуска кода:
0:00:41.392303
30001 [0, 1, 2, 3, 4, 5, 5, 6, 7, 8]
См. список заказанных элементов 1 30 000 нулевого потребления не является коротким, потратил 41 секунду, это видно по срезу, истекшему последовательно расположенным.
Полученный результат:
- Пузырьковая сортировка - 41
- Сортировка выбором (два слоя для) - 47
- Сортировка выбором (макс. микс) - 14
- Сортировка вставками — 0,007398
вопрос: Невероятно, что скорость сортировки вставками требует гораздо меньше времени, чем два других метода сортировки. Почему это?
На самом деле сортировка вставками использует только 1 уровень цикла for, а не 2 уровня цикла for, как пузырьковое и выборочное.Может ли это освежить введение временной сложности на приведенном выше рисунке?
вопрос: И результаты двух разных методов сортировки выбором такие разные, почему так? ? ?
Пожалуйста, выскажите свое мнение в разделе комментариев