В алгоритмах информатики и структурах данных большую часть времени мы рассматриваем анализ сложности Big-O в качестве эталона. Но анализ Big-O не всегда является лучшим вариантом. Здесь, в этой статье, я расскажу о том, как амортизированная сложность имеет гораздо больше смысла в некоторых случаях.
🎯 Амортизированное время – это способ выразить временную сложность, когда алгоритм имеет очень плохую временную сложность только раз в то время, помимо временной сложности, которая происходит большую часть времени. Хорошим примером может быть ArrayList , который представляет собой структуру данных, содержащую массив и может быть расширен.
В обычном массиве размер массива предопределен. Следовательно, вставки в массив равны O(1) или постоянному времени. Но когда мы используем ArrayList, размер является переменным и может увеличиваться/уменьшаться в зависимости от входных данных. Каждый ArrayList имеет начальную емкость. В основном начальная вместимость составляет 10 человек.
Теперь, когда мы хотим вставить более 10 элементов, необходимо выполнить три шага: 1.Создать новый массив двойного размера (2N) 2.Скопировать все предыдущие элементы (N) 3.Добавьте новый элемент.
Когда ArrayList достигает в нем емкости массива, он создает новый массив с удвоенным размером старого массива и копирует все элементы из старого массива в новый массив. В ArrayList существуют две временные сложности; одна – O(1), а другая – O(n).
Первый вид – O(1), как показано ниже:
Второй вид – O (N), как показано ниже:
Таким образом, в случае динамического массива мы можем сказать, что:
Вставка занимает O (n), когда емкость достигнута, а амортизированное время для каждой вставки равно O(1).
Заключительные слова:
В терминах Oracle (которые подразумеваются молчаливо) и говорят о списке:
🎯 add метод (синоним – “метод добавления”) всегда означает логическое add(E) 🎯 insert метод всегда означает логическое добавление(int index, E)
Когда Oracle пишет:
Операция добавления выполняется за амортизированное постоянное время, то есть для добавления n элементов требуется O(n) времени.
это означает:
Сложность одной логической операции добавления(E) амортизируется O(1).
Это не может быть просто O (1) асимптотическим (всегда), потому что редко нам нужно увеличивать емкость массива. Эта единственная операция добавления, которая на самом деле является операцией “создать новый больший массив, скопировать в него старый массив, а затем добавить один элемент в конец”, имеет асимптотическую сложность O (n), потому что копирование массива при увеличении емкости списка составляет O (n), сложность увеличения плюс добавление составляет O (n) [вычисляется как O(n) +(n)]. Без этой операции увеличения емкости сложность добавления была бы O(1), элемент всегда добавляется (добавляется) в конец массива (максимальный индекс). Если бы мы “добавили”) не в конец массива, нам нужно было бы переместить крайние правые элементы (с большими индексами), а сложность для одной такой операции была бы O (n).
Теперь для одной операции добавления асимптотическая сложность равна O (1) для добавления без увеличения емкости и O (n) для добавления с увеличением емкости (что случается очень редко).
Амортизированная сложность одной операции добавления равна O(1). Это отражает тот факт, что редкие O (n) операции роста и добавления “разбавляются” гораздо более многочисленными O (1) операциями добавления без роста, поэтому “в среднем” одна операция равна O (1).
“Асимптотическая сложность” n операций сложения равна O (n). Но здесь мы говорим о сложности n операций, а не о сложности одной операции. Это не строгий способ выразить это так (“асимптотическая сложность”), но в любом случае. Амортизированная сложность n операций имеет еще меньше смысла.
Наконец, сложность логической операции add(int index, E) для одной операции всегда равна O(n). Если он вызывает рост, то это O(n) + O(n) [grow + insert], но 2*O(n) совпадает с O(n).
Таким образом, в таких случаях Амортизированный анализ имеет больше смысла.
Я предоставляю приведенные ниже ссылки для справки и лучшего понимания.
Часть теории Гаурава Сена
Кодирующая часть Гаурава Сена
0612 ТЕЛЕВИЗОР с первым БОТАНИКОМ
Шпаргалка Big O
Если вам понравился этот пост, то, пожалуйста, оставьте сердечко ❤️
И если у вас есть какие-либо вопросы или предложения ко мне, пожалуйста, оставьте их на панели обсуждений.
Оригинал: “https://dev.to/the_unconventional_coder/amortized-time-complexity-j2e”