Что такое временная сложность?
Согласно Википедии, «В информатике временная сложность - это вычислительная сложность, которая описывает количество компьютерного времени, необходимого для выполнения алгоритма».
Проще говоря, временная сложность определяется как время, необходимое алгоритму для выполнения. Обычно это зависит от размера ввода.
Важность временной сложности
Очень важно позаботиться о пространстве и времени любого алгоритма. Ведь у нас есть несколько способов решить любую проблему. Таким образом, мы должны проанализировать различные алгоритмы и выяснить, какой из них лучше всего в зависимости от использования времени и пространства при разных размерах входных данных.
Пример: - Найти число, простое или нет.
Подход 1
Это самый простой подход с временной сложностью O (n)
Подход 2
Это модифицированный подход с временной сложностью O (n / 2)
Подход 3
В этом подходе временная сложность будет равна O (√n).
Все выполняют одинаковую работу, но из всех трех подходов подход 3 - самый быстрый.
Скорость роста определяется как скорость, с которой время работы алгоритма увеличивается по мере увеличения размера входных данных.
Три типа анализа
В идеале мы должны проверить алгоритм для разных случаев.
- Худший случай - случай, когда время работы является максимальным по сравнению с другими случаями.
- Среднее значение - среднее время работы.
- Лучший случай, в котором время работы минимально.
Пример: Нахождение числа X в массиве {1,5,9,18,20,25,49}
Если X = 1, то это лучший случай
Если X = 49, это наихудший случай
Любое число от 1 до 49 соответствует среднему регистру.
Асимптотические обозначения
Обозначения, необходимые для представления временной и пространственной сложности любого данного алгоритма, известны как асимптотические обозначения.
- Обозначение Big-Oh (O)
Это дает нам верхнюю границу времени работы алгоритма. Поскольку он дает максимальное время, он дает нам временную сложность наихудшего случая.
O (g (n)) = {f (n): существуют положительные константы c и n0 такие, что 0 ‹= f (n)‹ = c * g (n) для всех n ›= n0 }
2. Обозначение Омега (Ω)
Это дает нам нижнюю границу времени работы алгоритма. Поскольку он дает минимальное время, поэтому он дает нам временную сложность наилучшего случая.
O (g (n)) = {f (n): существуют положительные константы c и n0 такие, что 0 ‹= c * g (n)‹ = f (n) для всех n ›= n0 }
3. Тета-нотация ( Θ )
Он дает нам как верхнюю, так и нижнюю границу времени работы алгоритма.
O (g (n)) = {f (n): существуют положительные константы c1, c2 такие, что 0 ‹= c1 * g (n)‹ = f (n) ‹= c2 * g (n) для все n ›= n0}
В основном мы представляем временную сложность в нотации Big-Oh, потому что она дает нам время, необходимое для наихудшего случая, и мы всегда должны оценивать любой алгоритм по временной сложности наихудшего случая.
Различные типы временной сложности
- O (1) - Константа
Если время, затрачиваемое алгоритмом, не меняется с увеличением размера входных данных, то временная сложность этого алгоритма равна O (1).
Пример: - Сложение двух чисел
2. O (n) - линейный
Если скорость роста алгоритма линейно зависит от размера ввода.
Пример: - Сумма n чисел.
3. O (log n) - логарифмический
Если количество входов уменьшается вдвое с каждым шагом. Тогда временная сложность этого алгоритма равна O (log n).
Пример: - Двоичный поиск
4. O (n²) - квадратичный
Если скорость роста алгоритма равна n², то временная сложность будет O (n²).
Пример: - Пузырьковая сортировка
5. O (n Log n) - линейный
Сортировка слиянием, быстрая сортировка - вот некоторые примеры такого типа временной сложности.
Временная сложность от лучшего к худшему
1 ‹log n‹ n ‹n log n‹ n² ‹n³‹ 2 ^ n ‹n
Как рассчитать временную сложность
- Время, затрачиваемое на основные арифметические операции, постоянно.
- Если цикл выполняется n раз, то временная сложность этого цикла будет O (n).
В приведенном ниже коде 2 цикла выполняются n раз. таким образом, сложность времени будет O (n²).
Почему мы не можем рассчитать временную сложность в секундах?
Сколько времени будет работать алгоритм, полностью зависит от мощности вашего компьютера. Таким образом, если какой-то код выполняется в вашей системе за 1 секунду. В другой системе это может занять другое время. Поэтому мы вычисляем его в асимптотических обозначениях, которые дают нам меру того, как время будет изменяться при вводе
Проблемы с практикой
- Найдите временную сложность следующих фрагментов кода
for(i= 0 ; i < n; i++){
cout<< i << " " ;
i++;
}
Цикл имеет максимальное значение n, но i будет увеличиваться дважды в цикле for, что займет половину времени. Таким образом, временная сложность составляет O (n / 2), что эквивалентно O (n).
2. Найдите временную сложность следующих фрагментов кода.
int i = n;
while(i){
cout << i << " ";
i = i/2;
}
В этом случае после каждой итерации значение i превращается в половину своего предыдущего значения. Так что сериал будет такой:. Таким образом, временная сложность равна O (log n).
3. Найдите временную сложность следующих фрагментов кода.
for(i= 0 ; i < n; i++){
for(j = 0; j<n ;j++){
cout<< i << " ";
}
}
И внутренний, и внешний цикл выполняются n раз. Таким образом, для одного значения i, j повторяется n раз, для n значений i, j будет повторяться всего n * n = n 2 раза. Таким образом, временная сложность O (n 2).
4. Найдите временную сложность следующих фрагментов кода.
if(i > j ){
j>23 ? cout<<j : cout<<i;
}
В коде есть два условных оператора. Каждый условный оператор имеет временную сложность = O (1), для двух из них это O (2), что эквивалентно O (1), которое является константой.
