Цель разработки алгоритма — найти наиболее эффективный алгоритм для данной задачи, а эффективность обычно измеряется с точки зрения временной сложности». — Джон Клейнберг и Эва Тардос, авторы книги «Дизайн алгоритмов.
Введение
В области информатики и разработки алгоритмов временная сложность играет важную роль в определении эффективности и масштабируемости алгоритмов. Как компьютерные программы имеют дело с большими и сложными наборами данных и операций. Крайне важно проанализировать и оптимизировать время и пространство, которое алгоритму требуется для выполнения задач. В этот момент на сцену выходит сложность времени.
Понимание временной сложности необходимо для разработки эффективных алгоритмов, а эффективные алгоритмы — ключ к решению сложных вычислительных задач». — Анани Левитин, профессор компьютерных наук и автор книги «Введение в проектирование и анализ алгоритмов.
Временная сложность относится к измерению того, сколько времени требуется алгоритму для выполнения при увеличении размера входных данных. Это помогает анализировать эффективность и производительность алгоритма. Это позволяет разработчикам алгоритмов принимать обоснованные решения и использовать меньше ресурсов (времени и пространства) и получать эффективные результаты для различных сценариев.
В целом, временная сложность является важной концепцией для понимания, когда речь идет о разработке и оптимизации алгоритмов. Сосредоточив внимание на эффективной временной сложности, вы можете создавать программы, которые работают быстро и эффективно и лучше справляются с большими наборами данных и сложными задачами.
«Структуры данных и алгоритмы являются строительными блоками информатики. Без них у нас не было бы возможности обрабатывать, хранить и анализировать большие объемы информации». — Марк Аллен Вайс, профессор компьютерных наук и автор книги «Структуры данных и анализ алгоритмов в Java».
В этой статье вы узнаете о временной сложности и обозначениях временной сложности, а также о том, как вычислить временную сложность. Эта статья будет продолжена еще двумя статьями, чтобы завершить тему временной сложности. Я постараюсь сделать эту концепцию понятной для вас. Если у вас есть вопросы, то спрашивайте.
Обозначение большого O
Обозначение Big O используется для указания верхней границы временной сложности алгоритма по мере увеличения размера входных данных. Это математическое обозначение, используемое для описания масштабирования производительности алгоритма по мере увеличения размера входных данных.
Какова верхняя граница временной сложности алгоритма?
Важно учитывать верхнюю границу временной сложности алгоритма, потому что она покажет нам, как алгоритм будет работать при увеличении размера входных данных. Здесь следует отметить, что верхняя граница сложности алгоритма не всегда точна —
«это означает, что иногда алгоритм работает намного лучше, чем предполагает верхняя граница, особенно при небольших размерах входных данных или когда применяется определенная оптимизация».
Однако верхняя граница обеспечивает полезную основу для понимания того, как алгоритм будет масштабироваться по мере увеличения размера входных данных.
В нотации Big O временная сложность алгоритма выражается как функция размера входных данных.
Например:
Постоянное время:
O(1) Алгоритм, выполнение которого занимает постоянное время, независимо от размера входных данных. Например, доступ к элементу массива по индексу или поиск значения в словаре.
Java-программа для доступа к элементу массива занимает постоянное время.
public class ConstantTimeExample {
public static void main(String[] args) {
int[] arr = {1, 2, 3, 4, 5};
int index = 2;
int element = arr[index]; // Accessing an element in an array by index takes constant time
System.out.println("The element at index " + index + " is " + element);
}
}
Эта операция доступа к элементу занимает постоянное время, потому что от размера массива не зависит, будет ли его размер 5 или 5 миллионов.
Но тут возникает вопрос, почему это не зависит от размера массива. ведь все-таки мы должны получить доступ к элементу из массива?
Ответ заключается в том, что на большинстве современных компьютеров доступ к элементу массива по индексу занимает постоянное время (O(1)), поскольку массив хранится в непрерывной памяти (непрерывная память относится к схеме распределения памяти, в которой все элементы массива хранятся в последовательных ячейках памяти.). Каждый элемент массива расположен по фиксированному адресу памяти, поэтому для доступа к элементу по индексу компьютер просто вычисляет адрес памяти элемента, используя простую математическую формулу.
address = base_address + (index * element_size)
где base_address — адрес памяти первого элемента массива, index — индекс элемента, к которому мы хотим получить доступ, а element_size — размер (в байтах) каждого элемента в массиве.
Этот расчет занимает постоянное количество времени, независимо от размера массива. Однако в некоторых ситуациях доступ к элементу в массиве может занять больше времени, чем постоянное, например, когда массив не хранится в непрерывной памяти или когда нам нужно искать элемент, а не обращаться к нему по индексу.
Логарифмическое время: O(log n)
По мере увеличения размера входных данных время работы алгоритма увеличивается. Но она не увеличивается линейно, она увеличивается медленнее.
Двоичный поиск является примером с логарифмической временной сложностью:
Двоичный поиск — это алгоритм, используемый для поиска элемента в отсортированном массиве. Массив многократно делится пополам, и мы проверяем, находится ли элемент, который мы хотим найти, в левой или правой половине.
Вот пример реализации бинарного поиска с логарифмической временной сложностью в Java:
У нас есть отсортированный массив
arr = [2, 4, 6, 8, 10, 12, 14, 16]
Мы хотим найти элемент 10 в этом массиве, используя алгоритм бинарного поиска.
- Сначала мы устанавливаем левый и правый указатели на первый и последний индекс массива соответственно:
left = 0 right = 7
Итак, 0 и 7 — это первый и последний индекс соответственно, 0=2 & 7=16
2. Затем мы вычисляем средний индекс массива, усредняя значения левого и правого
mid = (left + right) / 2 = 3 +> 0+7/2 = 3
3. Сравниваем средний элемент arr[mid] с целевым элементом 10. Поскольку arr[mid] (средний элемент, равный 8 по индексу 3) меньше 10, мы можем удалить левую половину массива и обновить левый указатель до mid + 1:
left = mid + 1 = 4
Когда средний элемент массива меньше целевого элемента, мы знаем, что целевой элемент может присутствовать только в правой половине массива, так как массив отсортирован в порядке возрастания. Следовательно, мы можем исключить левую половину массива из рассмотрения на следующей итерации.
Для этого мы устанавливаем левый указатель на mid + 1, что означает, что новый диапазон поиска будет начинаться с элемента сразу справа от среднего элемента.
Если средний элемент массива больше целевого элемента, мы знаем, что целевой элемент будет найден в левой половине массива. В этом случае мы устанавливаем правый указатель на mid - 1, что означает, что новый диапазон поиска будет заканчиваться на элементе сразу слева от среднего элемента.
Повторяя эти шаги рекурсивно, мы можем эффективно искать целевой элемент в отсортированном массиве, используя алгоритм бинарного поиска с логарифмической временной сложностью.
4. Повторяем шаги 2–3 с новыми значениями left и right:
mid = (left + right) / 2 = 5 arr[mid] = 12 > 10 right = mid - 1 = 4
5. Повторяем шаги 2–3 с обновленными значениями left и right:
mid = (left + right) / 2 = 4 arr[mid] = 10 = 10 return mid = 4
Поэтому алгоритм бинарного поиска возвращает индекс 4, который соответствует элементу 10 в массиве.
Здесь временная сложность этого алгоритма равна логарифмической O(log n), где n — размер массива. Здесь размер массива равен 8, поэтому алгоритму бинарного поиска требуется не более log2(8) = 3 шагов, чтобы найти целевой элемент. Это демонстрирует логарифмическую временную сложность алгоритма бинарного поиска.
log2(8) = 3 откуда взялось 2?
В информатике функция логарифма обычно записывается как log2, что известно как логарифм по основанию 2.
Логарифм числа по основанию 2 говорит вам, сколько раз вы можете разделить это число на 2, прежде чем вы получите результат 1 или меньше. Например, логарифм числа 8 по основанию 2 равен 3, потому что вы можете разделить 8 на 2 три раза, чтобы получить 1 или меньше:
8 / 2 = 4 4 / 2 = 2 2 / 2 = 1
Точно так же логарифм по основанию 2 числа 16 равен 4, потому что вы можете разделить 16 на 2 четыре раза, чтобы получить 1 или меньше:
16 / 2 = 8 8 / 2 = 4 4 / 2 = 2 2 / 2 = 1
В контексте алгоритмов и структур данных логарифм по основанию 2 полезен, потому что он дает нам представление о том, сколько раз нам нужно выполнить определенную операцию с набором данных заданного размера для достижения определенного результата.
В случае бинарного поиска на каждом шаге мы делим размер оставшегося массива на 2, что соответствует логарифму по основанию 2 размера массива. В предыдущем примере размер массива равен 8, и мы можем найти, сколько раз нам нужно разделить 8 на 2, чтобы получить значение 1 или меньше.
Линейное время: O(n)
По мере увеличения размера входных данных время, необходимое для выполнения алгоритма, также пропорционально увеличивается. Линейный поиск является примером линейной временной сложности. При линейном поиске мы перебираем каждый элемент массива, чтобы найти целевой элемент. Если размер массива равен n, то временная сложность линейного поиска в наихудшем случае составляет O(n).
В целом, алгоритмы с линейной временной сложностью считаются эффективными, поскольку время, необходимое для их выполнения, растет линейно с размером входных данных.
Конечно, вот пример реализации алгоритма с линейной временной сложностью на Java:
Рассмотрим задачу нахождения суммы всех элементов массива. Один из способов решить эту проблему — перебрать каждый элемент массива и добавить его к текущей сумме. Вот пример реализации этого алгоритма на Java:
public static int sumArray(int[] arr) {
int sum = 0;
for (int i = 0; i < arr.length; i++) {
sum += arr[i];
}
return sum;
}
В этом алгоритме мы инициализируем переменную `sum` to 0.. Затем мы перебираем каждый элемент массива, используя цикл `for`, и добавляем каждый элемент в `sum`. Наконец, мы возвращаем `sum` как сумму всех элементов массива.
Временная сложность этого алгоритма в наихудшем случае равна O(n), так как нам нужно выполнить итерацию по каждому элементу массива ровно один раз. Этот алгоритм является примером алгоритма с линейной временной сложностью, поскольку время, необходимое для его выполнения, увеличивается линейно с размером входных данных (т. Е. Количеством элементов в массиве).
Однако в некоторых случаях можно разработать алгоритмы с еще большей временной сложностью для конкретных задач.
Бинарный поиск
Алгоритм обычно используется для поиска определенного элемента в отсортированном массиве. Стандартная временная сложность — O(log n), где n — размер массива. Однако, если мы знаем, что массив отсортирован и искомый элемент находится по определенному индексу, мы можем использовать алгоритм с улучшенной временной сложностью O(1), например, просто получить доступ к элементу напрямую по индексу.
Сортировка подсчета
Алгоритм используется для сортировки массива с известным диапазоном значений. Стандартная временная сложность — O(n log n), где n — размер массива. Однако, если диапазон значений невелик, мы можем использовать алгоритм с улучшенной временной сложностью O (n), такой как сортировка по счету. Сортировка подсчета работает, подсчитывая количество вхождений каждого значения в массиве, а затем восстанавливая отсортированный массив путем повторения подсчетов.
Резюме этой статьи
Давайте общаться в Linked In
