Big O performance of common functions of different Java Collections.
| List | Add | Remove | Get/Read | Contains | Next | Data Structure |
|---|---|---|---|---|---|---|
| [] | O(n) | O(n) | O(1) | O(n) | O(1) | Array |
| List | O(1)* | O(n) | O(n) | O(n) | O(1) | Array |
| ArrayList | O(1) | O(n) | O(1) | O(n) | O(1) | Array |
| LinkedList | O(1) | O(1) | O(n) | O(n) | O(1) | Linked List |
| CopyOnWriteArrayList | O(n) | O(n) | O(1) | O(n) | O(1) | Array |
| Set | Add | Remove | Contains | Next | Size | Data Structure |
|---|---|---|---|---|---|---|
| HashSet | O(1) | O(1) | O(1) | O(h/n) | O(1) | Hash Table |
| LinkedHashSet | O(1) | O(1) | O(1) | O(1) | O(1) | Hash Table + Linked List |
| EnumSet | O(1) | O(1) | O(1) | O(1) | O(1) | Bit Vector |
| TreeSet | O(log n) | O(log n) | O(log n) | O(log n) | O(1) | Red-black tree |
| CopyOnWriteArraySet | O(n) | O(n) | O(n) | O(1) | O(1) | Array |
| ConcurrentSkipListSet | O(log n) | O(log n) | O(log n) | O(1) | O(n) | Skip List |
| Queue | Offer | Peak | Poll | Remove | Size | Data Structure |
|---|---|---|---|---|---|---|
| PriorityQueue | O(log n) | O(1) | O(log n) | O(n) | O(1) | Priority Heap |
| LinkedList | O(1) | O(1) | O(1) | O(1) | O(1) | Array |
| ArrayDequeue | O(1) | O(1) | O(1) | O(n) | O(1) | Linked List |
| ConcurrentLinkedQueue | O(1) | O(1) | O(1) | O(n) | O(n) | Linked List |
| ArrayBlockingQueue | O(1) | O(1) | O(1) | O(n) | O(1) | Array |
| PriorirityBlockingQueue | O(log n) | O(1) | O(log n) | O(n) | O(1) | Priority Heap |
| SynchronousQueue | O(1) | O(1) | O(1) | O(n) | O(1) | None! |
| DelayQueue | O(log n) | O(1) | O(log n) | O(n) | O(1) | Priority Heap |
| LinkedBlockingQueue | O(1) | O(1) | O(1) | O(n) | O(1) | Linked List |
| Map | Get | ContainsKey | Next | Data Structure |
|---|---|---|---|---|
| HashMap | O(1) | O(1) | O(h / n) | Hash Table |
| LinkedHashMap | O(1) | O(1) | O(1) | Hash Table + Linked List |
| IdentityHashMap | O(1) | O(1) | O(h / n) | Array |
| WeakHashMap | O(1) | O(1) | O(h / n) | Hash Table |
| EnumMap | O(1) | O(1) | O(1) | Array |
| TreeMap | O(log n) | O(log n) | O(log n) | Red-black tree |
| ConcurrentHashMap | O(1) | O(1) | O(h / n) | Hash Tables |
| ConcurrentSkipListMap | O(log n) | O(log n) | O(1) | Skip List |
Where h is the table capacity.
Big O performance of common functions of different C# Collections.
| List | Description | Add_Data | Remove | Get/Read | Sort | Index access |
|---|---|---|---|---|---|---|
| [] | as it is | O(n) | O(n) | O(1) | No | Yes |
| List | Массив с автоматическим изменением размера | O(1)* | O(n) | O(n) | No | No |
| ArrayList | as it is | O(1) | O(n) | O(1) | ? | ? |
| LinkedList | Двусвязный список | O(1) | O(1) | O(n) | No | No |
| Dictionary | Хеш-таблица | O(1) | O(1) | O(1) | No | No |
| HashSet | Хеш-таблица | O(1) | O(1) | O(1) | No | No |
| Queue | Циклический массив с автоматическим изменением | O(1)* | O(1) | - | No | No |
| Stack | Циклический массив с автоматическим изменением | O(1)* | O(1) | - | No | No |
| SortedDictionary<K,V> | Дерево бинарного поиска, в котором все элементы отсортированы на основе ключа | O(log n) | O(log n) | O(log n) | Yes (using keys) | No |
| SortedList<K,V> | Сортированный массив с автоматическим изменением размера | O(n) | O(n) | O(log n) | Yes (using keys) | Yes |
| SortedSet | Сортированная коллекция, содержащая только отличающиеся элементы | O(log n) | O(log n) | O(log n) | Yes (using keys) | No |
-
Под «амортизированной» производительностью в данном случае подразумевается, что некоторые операции могут показывать производительность O(n), но большинство операций будут показывать производительность O(1), поэтому средняя производительность по n операциям составит O(1).
-
Capacity — число элементов, которые могут храниться в List, прежде чем потребуется изменить размер, в то время как Count — количество элементов, которые фактически находятся в List. Capacity всегда больше или равно Count. Если Count превышает Capacity при добавлении элементов, емкость увеличивается путем автоматического перераспределения внутреннего массива перед копированием старых элементов и добавлением новых элементов. Если емкость значительно больше, чем число, и требуется уменьшить объем памяти, используемой List, можно уменьшить емкость, вызвав метод TrimExcess или явно задав для свойства Capacity более низкое значение. Если значение Capacity задано явно, внутренний массив также перераспределяется в соответствии с заданной емкостью, и все элементы копируются. Получение значения этого свойства является операцией O (1); Задание свойства является операцией O (n), где n — это новая емкость.
Для оценки производительности алгоритмов можно использовать разные подходы. Самый бесхитростный - просто запустить каждый алгоритм на нескольких задачах и сравнить время исполнения. Другой способ - математически оценить время исполнения подсчетом операций.
Рассмотрим алгоритм вычисления значения многочлена степени n в заданной точке x. Pn(x) = anxn + an-1xn-1 + ... + aixi + ... + a1x1 + a0
Алгоритм 1 - для каждого слагаемого, кроме a0 возвести x в заданную степень последовательным умножением и затем домножить на коэффициент. Затем слагаемые сложить.
Вычисление i-го слагаемого(i=1..n) требует i умножений. Значит, всего 1 + 2 + 3 + ... + n = n(n+1)/2 умножений. Кроме того, требуется n+1 сложение. Всего n(n+1)/2 + n + 1= n2/2 + 3n/2 + 1 операций.
Алгоритм 2 - вынесем x-ы за скобки и перепишем многочлен в виде Pn(x) = a0 + x(a1 + x(a2 + ... ( ai + .. x(an-1 + anx))).
Например, P3(x) = a3x3 + a2x2 + a1x1 + a0 = a0 + x(a1 + x(a2 + a3x))
Будем вычислять выражение изнутри. Самая внутренняя скобка требует 1 умножение и 1 сложение. Ее значение используется для следующей скобки... И так, 1 умножение и 1 сложение на каждую скобку, которых.. n-1 штука. И еще после вычисления самой внешней скобки умножить на x и прибавить a0. Всего n умножений + n сложений = 2n операций.
Зачастую такая подробная оценка не требуется. Вместо нее приводят лишь асимптотическую скорость возрастания количества операций при увеличении n.
Функция f(n) = n2/2 + 3n/2 + 1 возрастает приблизительно как n2/2 (отбрасываем сравнительно медленно растущее слагаемое 3n/2+1). Константный множитель 1/2 также убираем и получаем асимптотическую оценку для алгоритма 1, которая обозначается специальным символом O(n2) [читается как "О большое от эн квадрат"].
Это - верхняя оценка, т.е количество операций(а значит, и время работы) растет не быстрее, чем квадрат количества элементов. Чтобы почувствовать, что это такое, посмотрите на таблицу, где приведены числа, иллюстрирующие скорость роста для нескольких разных функций.
Если считать, что числа в таблице соответствуют микросекундам, то для задачи с n=1048576 элементами алгоритму с временем работы O(log n) потребуется 20 микросекунд, алгоритму со временем O(n) - 17 минут, а алгоритму с временем работы O( n2 ) - более 12 дней... Теперь преимущество алгоритма 2 с оценкой O(n) перед алгоритмом 1 достаточно очевидно.
Наилучшей является оценка O(1)... В этом случае время вообще не зависит от n, т.е постоянно при любом количестве элементов.
Таким образом, O() - "урезанная" оценка времени работы алгоритма, которую зачастую гораздо проще получить, чем точную формулу для количества операций.
Итак, сформулируем два правила формирования оценки O(). При оценке за функцию берется количество операций, возрастающее быстрее всего. То есть, если в программе одна функция, например, умножение, выполняется O(n) раз, а сложение - O(n2) раз, то общая сложность программы - O(n2), так как в конце концов при увеличении n более быстрые ( в определенное, константное число раз ) сложения станут выполнятся настолько часто, что будут влиять на быстродействие куда больше, нежели медленные, но редкие умножения. Символ O() показывает исключительно асимптотику!
При оценке O() константы не учитываются. Пусть один алгоритм делает 2500n + 1000 операций, а другой - 2n+1. Оба они имеют оценку O(n), так как их время выполнения растет линейно.
В частности, если оба алгоритма, например, O( nlog n ), то это отнюдь не значит, что они одинаково эффективны. Первый может быть, скажем, в 1000 раз эффективнее. O() значит лишь то, что их время возрастает приблизительно как функция nlog n.
Другое следствие опускания константы - алгоритм со временем O(n2) может работать значительно быстрее алгоритма O(n) при малых n... За счет того, что реальное количество операций первого алгоритма может быть n2 + 10n + 6, а второго - 1000000n + 5. Впрочем, второй алгоритм рано или поздно обгонит первый... n2 растет куда быстрее 1000000n.
Основание логарифма внутри символа O() не пишется. Причина этого весьма проста. Пусть у нас есть O( log2n). Но log2n=log3n/log32, а log32, как и любую константу, асимптотика - символ О() не учитывает. Таким образом, O( log2n) = O( log3n).
К любому основанию мы можем перейти аналогично, а значит и писать его не имеет смысла.
Математическое толкование символа O(). Определение O(g) - множество функций f, для которых существуют такие константы C и N, что |f(x)| <= C|g(x)| для всех x>N. Запись f = O(g) дословно обозначает, что f принадлежит множеству O(g). При этом обратное выражение O(g) = f не имеет смысла.
В частности, можно сказать, что f(n) = 50n принадлежит O(n2). Здесь мы имеем дело с неточной оценкой. Разумеется, f(n) <= 50n2 при n>1, однако более сильным утверждением было бы f(n) = O(n), так как для C=50 и N=1 верно f(n) <= Cn, n>N.
Другие виды оценок. Наряду с оценкой O(n) используется оценка Ω(n) [читается как "Омега большое от эн"]. Она обозначает нижнюю оценку роста функции. Например, пусть количество операций алгоритма описывает функция f(n) = Ω(n2). Это значит, что даже в самом удачном случае будет произведено не менее порядка n2 действий. ...В то время как оценка f(n) = O(n3) гарантирует, что в самом худшем случае действий будет порядка n3, не больше.
Также используется оценка Θ(n) ["Тэта от эн"], которая является гибридом O() и Ω(). Θ(n2) является и верхней и нижней асимптотической оценкой одновременно - всегда будет выполняться порядка n2 операций. Оценка Θ() существует только тогда, когда O() и Ω() совпадают и равна им.
Для рассмотренных выше алгоритмов вычисления многочлена найденные оценки являются одновременно O(), Ω() и Θ(). Если добавить к первому алгоритму проверки на x=0 в возведении в степень, то на самых удачных исходных данных(когда x=0) имеем порядка n проверок, 0 умножений и 1 сложение, что дает новую оценку Ω(n) вкупе со старой O(n2).
Как правило, основное внимание все же обращается на верхнюю оценку O(), поэтому, несмотря на "улучшение", алгоритм 2 остается предпочтительнее.
Итак, O() - асимптотическая оценка алгоритма на худших входных данных, Ω() - на лучших входных данных, Θ() - сокращенная запись одинаковых O() и Ω().
