具有绝对值的大O符号？

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|集合中的元素数量，如Kostub Deshmukh所提到的。

可以有更多的情况。