具有绝对价值的大O符号？ [英] Big O Notation with Absolute Value?

问题描述

我正在浏览一些编程面试问题书，我已经看到了对O（| A |）时间复杂性的引用。我从来没有看到这个符号的绝对值。

一些研究让我 Big O Cheatsheet 在图表部分引用该表示法。我正在研究的问题是关于分割一个数组，这实际上不是一个图形问题（尽管我冒险可能显示出我对该语句的无知）。

code> | A | 指的是数组的大小或者其他元素的数量，即 O（N）？

解决方案

集合论符号 | A | 是集合 A ，换言之，包含在集合 A 中的元素数目。

参考： http://www.mathsisfun.com/sets/symbols.html

I'm going through some programming interview question books, and I've seen reference to "O(|A|)" time complexity. I've never seen this notation with the absolute value given.

Some research led me to Big O Cheatsheet that references this notation under the graphs section. The problem I'm researching is about partitioning an array, which isn't really a graph question (though I risk perhaps showing my ignorance with that statement).

Does |A| refer to the magnitude of the array, or otherwise number of elements, i.e. O(N)?

解决方案

In set theory notation |A| is the cardinality of set A, in other words the number of elements contained in set A.

For Reference: http://www.mathsisfun.com/sets/symbols.html

这篇关于具有绝对价值的大O符号？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！