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

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

1. Эффективность алгоритма

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

1. Понятие сложности

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

2. Важность сложности

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

2. Временная сложность

Определение: В информатике временная сложность алгоритма представляет собой функциональную формулу T(N), которая количественно описывает время работы алгоритма. Временная сложность измеряет эффективность использования времени программы, так почему бы не рассчитать время ее выполнения?

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

Следовательно, при оценке степени распределения времени алгоритма время выполнения алгоритма не учитывается, а только количество выполненных инструкций.

Случай:

// 请计算⼀下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

Через наблюдение:
Количество основных операций, выполняемых Func1:
Т(Н)=Н²+ 2*N + 10

На практике, когда мы рассчитываем временную сложность, мы не рассчитываем точное количество выполнений программы. Подсчитать точное количество выполнений все равно очень затруднительно (разные предложения программного кода будут иметь разное количество скомпилированных инструкций (например). (это) вычисление точного количества выполнений не имеет большого значения, поскольку мы хотим только сравнить уровень роста программы алгоритма при расчете временной сложности, то есть разницу в T(N), когда N продолжает увеличиваться. Выше мы видели, что константы и члены младшего порядка мало влияют на результаты, когда N продолжает расти, поэтому нам нужно только вычислить приблизительное количество выполнений, которые может представить программа, чтобы увеличить порядок величины. Выражение сложности: обычно используется. Используйте асимптотическую нотацию Big O.

3. Пространственная сложность

Пространственная сложность — это также математическое выражение, которое представляет собой дополнительное пространство, временно выделяемое из-за потребностей алгоритма во время работы алгоритма.
Пространственная сложность — это не то, сколько байт памяти занимает программа. Поскольку при нормальных обстоятельствах размер каждого объекта не будет сильно различаться, поэтому пространственная сложность рассчитывается по количеству переменных.
Правила расчета пространственной сложности в основном аналогичны практической сложности, также используется асимптотическая нотация Big O.
Примечание. Пространство стека, необходимое при запуске функции (хранение параметров, локальных переменных, некоторой информации о регистрах и т. д.), определяется во время компиляции, поэтому сложность пространства в основном определяется дополнительным пространством, явно запрошенным функцией во время выполнения. . Конечно
Пространство не является ключевым фактором в современной разработке компьютеров, но следует избегать чрезмерных отходов. Слишком много отходов вызовет ненужные проблемы.

4. Асимптотическое представление «Большого О»

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

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

Худший случай: максимальное количество прогонов (верхняя граница) для любого входного размера.
Средний случай: ожидаемое количество прогонов для любого входного размера.
Лучший случай: минимальное количество прогонов (нижняя граница) для любого входного размера.
На практике асимптотическое представление Big O обычно фокусируется на верхней границе алгоритма, что является наихудшей рабочей ситуацией.

5. Случаи вычислительной сложности

1. Вычислить сложность функции Func1

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

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

Опустите код, который выполняется один раз, например count=0, этот код.
Сохраняйте количество выполнений кода, которые оказывают большое влияние на время выполнения.
Количество выполнений первого цикла равно выполнению двойного цикла NН
Второй цикл представляет собой слой выполнения цикла, умноженный на 2.Н
Третий цикл – 10 раз.
Сумма количества выполнений равна T(N)=N²+2*Н+10
Большой О представляет временную сложность, отбросьте небольшое влияние и возьмите предел.
НА²)

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

Функция Func1 применяется к размеру пространства. Например, int count = 0, она применяется к размеру пространства типа int M=10, а также к пространству типа int.
Эти два пробела также используются в цикле без дополнительного пространства приложения.
Размер пространства приложения постоянен
Пространственная сложность, выраженная в Big O, равна:
О(1)

2. Рассчитайте временную сложность Fun2.

void Func2(int N)
{
	int count = 0;
	for (int k = 0; k < 2 * N; ++k)
	{
		++count;
	} 
	int M = 10;
	while (M--)
	{
		++count;
	} 
	printf("%dn", count);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

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

Число запусков кода больше, чем число запусков первого цикла, равное N*2.
Второй цикл выполняется 10 раз.
Используйте большой О для обозначения временной сложности. Наибольшее влияние составляет 2*N. Предыдущий коэффициент опущен:
НА)

3. Рассчитайте временную сложность 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

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

Есть две неизвестные, и большее влияние оказывается на два цикла.
Первый цикл выполняется M раз
Второй цикл выполняется N раз.
Это должно быть неизвестное число, я не уверен, какое из них больше, а какое меньше, я не буду его опускать.
О(М+Н)

4. Рассчитайте временную сложность Func4.

void Func4(int N)
{
	int count = 0;
	for (int k = 0; k < 100; ++k)
	{
		++count;
	}
	printf("%dn", count);
}
1
2
3
4
5
6
7
8
9

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

Наибольшее влияние здесь оказывает цикл
Число запусков цикла равно 100.
фиксированная константа
О(1)

5. Рассчитаем временную сложность strchr

const char* strchr(const char* str, int character)
{
	const char* p_begin = str;
	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

Функция, выполняемая этой функцией, — найти нижний индекс символа в массиве.
Количество запусков здесь неизвестно.
Можно найти F(N)=1 за один раз.
В середине можно найти F(N)=N/2.
Он может быть найден в конце, или возвращается NULL, если не найден, F(N)=N
Big O принимает наихудший сценарий:
Временная сложность O(N).

6. Рассчитайте временную сложность Func5.

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

Это количество запусков связано с размером n, но оно не повторяется n раз. Это должно быть потому, что переменная цикла будет умножена на 2 во время цикла, и цикл быстро выскочит. значение переменной цикла cnt достигнет 1024.
Предполагая, что количество циклов равно x, тогда 2^Икс=н
х=логн
Таким образом, временная сложность равна: O(longn)

7. Рассчитаем сложность BubbleSor

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

Эта функция завершает сортировку по возрастанию пузырька.
Здесь есть цикл. Этот цикл представляет собой двухуровневый вложенный цикл.
Количество петель не определено.
В худшем случае внешний цикл выполняется n раз.
Тогда внутренний цикл будет выполняться (n-1)+(n-2)+(n-3)+……+2+1+0
представляет собой арифметическую последовательность, а сумма равна:

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

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

Дополнительного пространства для приложений нет, и используемое пространство является постоянным.
О(1)

8. Сложность вычисления факториальной рекурсии Fac

long long Fac(size_t N)
{
	if (0 == N)
		return 1;
	return Fac(N - 1) * N;
}
1
2
3
4
5
6

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

Рекурсивно N раз
Таким образом, временная сложность равна: O(N)

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

Каждый раз, когда вы рекурсируете, вам нужно подать заявку на место.
Рекурсивно N раз и применено к N раз в пространстве.
Пространственная сложность: O(N).