Обмен технологиями

한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina

Предисловие

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

Это можно понимать на двух уровнях. Данные существуют повсюду в нашей жизни, например, международные события, которые являются горячими темами в Douyin, снятие брони Юнчжэна и т. д. Наши пользователи могут видеть данные, которые Douyin хранит на внутреннем сервере. Но у всех этих данных есть одна особенность: все они находятся в горячем списке поиска Douyin, и этот список структурирован так, чтобы гарантировать, что данные находятся в фиксированном месте, чтобы пользователи могли их просматривать.

Кроме того, алгоритмы неотделимы от структур данных. Как мы только что сказали, структура данных регулярно хранит данные в структуре, поэтому эффективный доступ к данным из структуры — это алгоритм.

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

Алгоритмы имеют временную и пространственную сложность. Поскольку память компьютеров становится все больше и больше, временная сложность важнее пространственной.Итак, давайте сначала поймем временную сложность

концепция

Временная сложность, самое важное слово — время, здесь под временем понимается время выполнения программы. Если временная сложность меньше, то алгоритм оказывается лучше.Расчет временной сложности выражается функциональной формулой T(N)

Так почему бы нам заранее не рассчитать временную сложность этой программы и не написать код оптимального решения? Это связано с компьютерными проблемами.

1. Поскольку время выполнения программы связано со средой компиляции и конфигурацией работающей машины, например, программа-алгоритм использует старый компилятор.
   Компиляция с использованием нового компилятора и компиляция с использованием нового компилятора имеют разное время выполнения на одной и той же машине.
2. Одна и та же программа-алгоритм имеет разное время выполнения на старой машине с низкой конфигурацией и на новой машине с высокой конфигурацией.
3. А время можно проверить только после того, как программа написана, а не рассчитана и оценена посредством теоретического размышления перед написанием программы.

Давайте посмотрим на кусок кода:

// 请计算⼀下Func1中count语句总共执⾏了多少
次？
void Func1(int N)
{
int count = 0;
for (int i = 0; i < N ; ++ i)
{
for (int j = 0; j < N ; ++ j)
{
++count;
}
}
for (int k = 0; k < 2 * N ; ++ k)
{
++count;
}
int M = 10;
while (M--)
{
++count;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

Если вы посмотрите на этот код на основе количества выполнений count, он должен быть:
Т (Н) = Н2 + 2 ∗ Н + 10
• N = 10 Т(N) = 130
• N = 100 Т(N) = 10210
• N = 1000 Т(N) = 1002010

В этот раз кто-то сказал, что int count=0 не считается;

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

Асимптотическое представление Big O

Обозначение Big O: это математический символ, используемый для описания асимптотического поведения функции; здесь он используется для обозначения расчетной временной сложности;

Значит, здесь оно по-прежнему считается T(N)? Если да, то нам не нужно использовать для его представления другой символ. Это включает в себя правила подсчета O:

1. В функциональной формуле временной сложности T(N) сохраняются только члены высшего порядка, а члены низшего порядка удаляются, поскольку, когда N продолжает увеличиваться, влияние членов низшего порядка на результат становится все меньше и меньше. Когда N бесконечно, его можно игнорировать.
2. Если член высшего порядка существует и не равен 1, удалите постоянный коэффициент этого члена, потому что по мере того, как N продолжает расти, этот коэффициент будет оказывать все меньшее и меньшее влияние на результат. Когда N бесконечно, его можно игнорировать.
3. Если в T(N) нет элементов, связанных с N, а есть только постоянные элементы, замените все аддитивные константы константой 1.

Затем посмотрите на приведенное выше T(N)=N^ 2 + 2 ∗ N + 10. Самый высокий порядок здесь — N2, поэтому, удаляя другие младшие порядки, сложность равна (ON^2)

Небольшой измельчитель

// 计算Func3的时间复杂度？
void Func3(int N, int M)
{
int count = 0;
for (int k = 0; k < M; ++ k)
{
++count;
}
for (int k = 0; k < N ; ++
k)
{
++count;
}
printf("%dn", count);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

Здесь T(N)=M+N, тогда давайте снова посчитаем O(N) M и N здесь одного порядка, поэтому они не подчиняются первому правилу и не соответствуют второму и третьему правилам. , поэтому o(N+M), тогда кто-то спросил, что, если N больше M, должно ли оно быть O(N) Вопрос в том, как узнать, что N больше M? Что, если M больше N, поэтому мы останемся здесь на всякий случай.

// 计算strchr的时间复杂度？
const char * strchr ( const char
 * str, int character)
{
const char* p_begin = s;
while (*p_begin != character)
{
if (*p_begin == '0')
return NULL;
p_begin++;
}
return p_begin;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

Здесь ищем позицию персонажа в str. Здесь добавлю очко знаний:

• Наш расчет O обычно представляет собой наихудшую сложность алгоритма.
  Здесь его можно разделить на три уровня сложности:
  1. Лучший сценарий
  Чтобы найти символ в первой позиции строки, выполните следующие действия:
  F (N) = 1, сложность o(1)

2. Средняя ситуация:
Чтобы найти символ в середине строки, выполните следующие действия:
Ф (Н) = Н/2, О(Н/2)

3. Наихудший сценарий
Чтобы найти символ в последней позиции строки, выполните следующие действия:
Ф(Н) = Н,О(Н)

// 计算BubbleSort的时间复杂度？
void BubbleSort(int* a, int n)
{
assert(a);
for (size_t end = n; end > 0; --end)
{
int exchange = 0;
for (size_t i = 1; i < end; ++i)
{
if (a[i-1] > a[i])
{
Swap(&a[i-1], &a[i]);
exchange = 1;
}
}
if (exchange == 0)
break;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

В худшем случае, поскольку сохраняется старший порядок и удаляется n/2 (первый элемент), а коэффициент (второй элемент) игнорируется, он равен ON^2.

void func5(int n)
{
int cnt = 1;
while (cnt < n)
{
cnt *= 2;
}
}
1
2
3
4
5
6
7
8

Когда n=2, количество выполнений равно 1
Когда n=4, количество выполнений равно 2
При n=16 количество выполнений равно 4
Предполагая, что количество выполнений равно x, тогда 2
х = н
Следовательно, количество выполнений: x = log n
Следовательно: временная сложность func5 в худшем случае равна:
O(log2^n)

В разных книгах используются разные способы выражения. Вышеуказанные способы написания не сильно отличаются. Мы рекомендуем использовать log n.

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

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

Уведомление

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

пример 1:

// 计算BubbleSort的时间复杂度？
void BubbleSort(int* a, int n)
{
assert(a);
for (size_t end = n; end > 0; --end)
{
int exchange = 0;
for (size_t i = 1; i < end; ++i)
{
if (a[i-1] > a[i])
{
Swap(&a[i-1], &a[i]);
exchange = 1;
}
}
if (exchange == 0)
break;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

Кадр стека функций был определен во время компиляции.
Вам нужно только обратить внимание на дополнительное пространство, запрашиваемое функцией во время выполнения.
Дополнительное пространство для приложения BubbleSort
Существует ограниченное количество локальных переменных, таких как обмен, который использует постоянное количество дополнительного пространства.
Таким образом, пространственная сложность равна O (1).