Сложность времени
Временная сложность алгоритма — это общее количество времени, которое требуется алгоритму для завершения выполнения. ИЛИ временная сложность — это то, насколько быстро ваш алгоритм будет работать.
Проще говоря, каждый фрагмент кода, который мы пишем, требует времени для выполнения. Время, необходимое для запуска любого фрагмента кода, известно как временная сложность этого кода. Чем меньше временная сложность, тем быстрее выполнение.
Оперативная память, ОС, скорость процессора и оборудование влияют на время. В теоретических вычислениях, говоря о временной сложности, нас больше всего интересует время выполнения.
Если вы немного программировали раньше, вы, вероятно, задаетесь вопросом, как это может быть полезно для вас, потому что ваша программа выполнялась вовремя, даже когда вы не знали всей этой сложности персонала. Таким образом, время работы программы зависит не только от эффективности кода, но и от вычислительной мощности ПК.
Поскольку временная сложность используется для измерения времени алгоритмов, тип алгоритмов, которые вы будете использовать в небольшой программе, на самом деле не будет иметь значения, потому что процессор почти не выполняет никакой работы, хотя когда мы пишем код в профессиональной жизни, код не состоит из 200 или 300 строк, он обычно длиннее, поэтому используется много процессорной мощности. Если ваш код неэффективен с точки зрения структуры данных, вы можете оказаться в довольно щекотливой ситуации.
— временная сложность часто измеряется с точки зрения:
Постоянное время: O(1)
Говорят, что алгоритм работает за постоянное время, если он требует одинакового количества времени независимо от размера входных данных. Примеры:
- массив: доступ к любому элементу
- стек фиксированного размера: методы push и pop
- очередь фиксированного размера: методы enqueue и dequeue
Линейное время: O(n)
Говорят, что алгоритм работает за линейное время, если время его выполнения прямо пропорционально размеру входных данных, т. е. время растет линейно по мере увеличения размера входных данных. Примеры:
- массив: линейный поиск, обход, поиск минимума
- ArrayList: содержит метод
- очередь: содержит метод
Логарифмическое время: O(log n)
Говорят, что алгоритм работает за логарифмическое время, если время его выполнения пропорционально логарифму размера входных данных. Пример:
- бинарный поиск
Квадратичное время: O(n2)
Говорят, что алгоритм работает за логарифмическое время, если время его выполнения пропорционально квадрату размера входных данных. Примеры:
- пузырьковая сортировка, сортировка выбором, сортировка вставками
Это все..
Мы очень ценим ваши отзывы.
