Большая нотация с абсолютным значением?

Question

Я изучаю некоторые вопросы, связанные с интервью, и я видел ссылку на "O(|A|)" сложность времени. Я никогда не видел эту нотацию с приведенным абсолютным значением.

Некоторые исследования привели меня к Big O Cheatsheet, который ссылается на эти обозначения в разделе графиков. Проблема, которую я исследую, - это разбиение массива, что на самом деле не является вопросом графа (хотя я рискую, возможно, показать свое незнание с этим утверждением).

Имеет ли |A| значение величины массива или в противном случае количество элементов, то есть O(N)?

Answer 1

В теории множеств |A| - мощность множества A, другими словами количество элементов, содержащихся в наборе A.

Справочно: http://www.mathsisfun.com/sets/symbols.html

Answer 2

Вы увидите это обозначение всегда, когда A не является числом.

A может быть много вещей, поэтому |A| зависит от контекста. Например.

• A является вектором решетки, поэтому |A| длина вектора.
• A - (возможно, неизвестный) алгоритм (например, злоумышленник для шифрования), то |A| может быть сложностью этого алгоритма или длиной случайного битового вектора, который использует этот алгоритм.
• A - это набор, то есть |A| количество элементов в наборе, как упоминал Костуб Десмух.

Может быть еще много случаев.