Структура данных и серия алгоритмов (1): временная и пространственная сложность

алгоритм

предисловие

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

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

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

Рекомендуемый список книг

Я не несу ответственности за рекомендацию волны, конечно, ее широко хвалят. Просто прочитайте Алгоритмы.

Может вместе лучше смотрится

Начало работы: «Структура данных Dahua», «Иллюстрация алгоритма»

Системное обучение: «Описание структур данных и алгоритмов»

Том: «Алгоритмы (4-е издание)»

База

Если структуры данных и алгоритмы являются одной из основ программирования, то следующие понятия являются общими основами структур данных и алгоритмов:

  • временная сложность
  • космическая сложность

А их теоретическая основа такова:

  • Обозначение большого O
  • Немного математики

Хорошо, по одному.

базовая основа

Обозначение большого O

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

f(n) = logn,f(n) = n ^ 2

Координатная диаграмма:

在这里插入图片描述
Видно, что тенденция роста желтой кривой намного больше, чем у синей кривой. В это время n принимает значение только 30, если

n → \infty

Тогда разница между ними будет очень и очень большой. В области алгоритмов эту растущую тенденцию мы используем大O表示法Выражать. так

O(n^2)

означает纵坐标y的值следить横坐标nтенденция роста, которая

n^2

Изображение этой функции. закончено, оy轴К чему это относится, будет сказано позже.

несколько математических

В обозначении большого O, упомянутом выше, мы можем

n→\infty （式1）

посмотри на ситуацию. Например

n^2 + n + 1 （式2）

, когда в式1В случае , потому что обозначение Big O выражает тенденцию к увеличению значения оси y. Если n равно 1,100 млн соответственно, то очевидно, что решающим фактором является:

当n = 1 时:n^2 = 1, n = 1;
当n = 1亿时:n^2 = 1亿亿，n = 1亿。

Очевидно, да

n^2

. так

O(n^2 + n + 1) ≈ O(n^2)

. Что вы хотите этим сказать, хотя式2является полиномом, но в случае анализа Big-O мы рассматриваем только член, который оказывает наибольшее влияние на тенденцию роста. Доказательство также очень хорошее: тенденция роста, как следует из названия, представляет собой коэффициент роста, который эквивалентенy / x. Уравнение 2, разделенное на n, становится:

n + 1 + \frac{1}{n}, n → \infty

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

n^2

.

Общие функциональные изображения

В области алгоритмов есть несколько образов функций, которые необходимо освоить, как показано ниже:

在这里插入图片描述
В нотации большого O все они представляют тенденцию роста. Вы можете разделить на n и самостоятельно доказать, какое из них больше. То же самое верно и для рисунка. В заключение:

2 ^ n > n ^2 > nlog(n) > n > log(n) > 1(常数)

временная и пространственная сложность

Оценка производительности алгоритма заключается в том, чтобы посмотреть на время работы и занимаемый объем памяти. Почему эти два параметра? Я думаю, что это должно быть так: В сочетании с архитектурой фон Неймана компьютер состоит из: памяти, вычислителя, контроллера и устройств ввода и вывода. Устройства ввода-вывода и контроллеры учитывать не нужно, поэтому остается память и калькуляторы. Разве алгоритм не просто сокращает объем вычислений и памяти на одной машине? По моему скромному мнению.

Ну так это приводит к时间复杂度а также空间复杂度Концепция чего-либо.

временная сложность

В приведенной выше нотации большого O значение координат оси Y не было специально определено. Мы предполагаем, что время, затрачиваемое машиной на выполнение каждой инструкции, одинаково, например, 1 единица времени, поэтому оно эквивалентно единице времени, необходимой для выполнения c инструкций, равной c. При анализе временной сложности алгоритма мы выражаем ось ординат большой нотации O как время, затрачиваемое на выполнение программы (или количество раз выполнения инструкции), поэтому: Временная сложность O(n) выражается как тенденция к увеличению времени, необходимого для правильного выполнения программы. и конкретные

O(n^2) 是否大于O(nlogn)

Глядя на функцию в скобках, то есть на картинку выше, мы видим, что она больше.

космическая сложность

Как и временная сложность, при расчете пространственной сложности O(n) представляет тенденцию к увеличению пространства, затрачиваемого программой на правильное выполнение, что на самом деле проще, чем сценарий временной сложности.

простое упражнение

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

void atom(int n) {
	int arr[n];
	int i;
	
	for (int i = 0; i < n; i++) {
		arr[i] = i;
	}
}

Временная сложность такова: независимо от того, насколько велико n, строки 2 и 3 выполняются 1 раз, тело цикла for в строке 5 выполняется n раз, а тело цикла for в строке 6 выполняется n раз, поэтому общее это: n + n + 1 + 1 , мы изучили, только посмотрите на наиболее влиятельные, затем это 2n, который далее упрощается до нескольких основных функций, и, наконец, n. так:

Временная сложность: O(n).

Сложность пространства такова: i занимает 1 единицу, а массив arr занимает n, поэтому в итоге:

Сложность пространства: O (n)

Категории