Полезные ссылки:
- [Видео](https://www.youtube.com/watch?v=cXCuXNwzdfY), в котором наглядно рассказывается данная тема
### Time Complexity (Временная сложность)
Это мера, которая показывает, сколько операций алгоритм выполняет в зависимости от размера входных данных. Она выражается как функция: например, `f(n) = 2n + 3`, где `n` — размер входных данных.
### Asymptotic Complexity (Асимптотическая сложность)
Это упрощённый вариант временной сложности, который описывает, как алгоритм будет работать на очень больших данных.
Асимптотическая сложность часто выражается через "Большое O" (Big O), как, например, `O(n)` или `O(n^2)`.
Асимптотическая сложность может быть описана с использованием различных нотаций, таких как:
- **Big O (O)**: Описывает верхнюю границу времени выполнения алгоритма.
- **Big Ω (Omega)**: Описывает нижнюю границу времени выполнения алгоритма.
- **Big Θ (Theta)**: Описывает точную асимптотическую сложность, когда верхняя и нижняя границы совпадают.
##### Большое О (Big O)
Это специфическая нотация для описания верхней границы асимптотической сложности. Иными словами, Big O даёт "пессимистическую оценку" — сколько максимально времени алгоритм потребует для выполнения при очень больших входных данных.
Если алгоритм имеет временную сложность `f(n) = 3n^2 + 4n + 5`, его асимптотическая сложность в нотации Big O будет `O(n^2)`.
[[Классы асимптотической сложности]]
##### Дополнительная информация
Термин "асимптотическая сложность" (asymptotic complexity) происходит от слова "асимптота" (asymptote), которое в математике означает линию или кривую, к которой функция приближается при стремлении аргумента к определенному значению (обычно бесконечности). В контексте анализа алгоритмов, асимптотическая сложность описывает поведение алгоритма при стремлении размера входных данных к бесконечности.
Основная идея асимптотического анализа в том, чтобы сосредоточиться на "долгосрочном" поведении функции производительности, игнорируя константы и младшие члены. Это особенно полезно, когда важным является понимание того, как алгоритм будет масштабироваться для очень больших объемов данных.
### В чем разница между "Time Complexity" и "Asymptotic Complexity"
1. **Детализация**: Временная сложность дает полное представление о количестве операций, включая коэффициенты и константы (например, `2n + 3`). Асимптотическая сложность это упрощает, игнорируя константы и сосредоточиваясь на самой "быстрорастущей" части (например, `O(n)`).
2. **Сфера применения**: Временная сложность чаще используется для конкретного случая или для малых данных, а асимптотическая — для общего представления о производительности алгоритма на больших данных.
### Пример
```csharp
public void ExampleFunction(int[] array)
{
int sum = 0; // 1 операция
for (int i = 0; i < array.Length; i++) // n операций
{
sum += array[i]; // n операций
}
Console.WriteLine(sum); // 1 операция
}
```
Если массив `array` содержит `n` элементов, то:
- Присваивание `int sum = 0` — это 1 операция.
- Цикл `for` будет выполняться `n` раз.
- Внутри цикла `for` у нас есть операция сложения `sum += array[i]`, которая также выполняется `n` раз.
- Вывод на консоль `Console.WriteLine(sum)` — это ещё 1 операция.
Таким образом, общее количество операций будет: `1 (инициализация sum) + n (цикл) + n (сложение внутри цикла) + 1 (вывод на консоль) = 2n + 2`
Это и будет временной сложностью нашего алгоритма в данном примере. Она описывает, как количество операций зависит от размера входного массива `n`.
Теперь, если говорить об асимптотической сложности этого алгоритма, мы можем упростить `2n + 2` до `O(n)`, потому что при очень больших `n` коэффициенты и константы становятся менее значимыми. Здесь `O(n)` — это асимптотическая сложность, которая говорит нам, что алгоритм будет работать пропорционально размеру входного массива.