蛮力解决方案的大 O 符号

Question

我正在解决 InterviewCake 的编程问题[1] and this problem[2] 让我很困惑。

 I have an array stock_prices_yesterday where:

- The indices are the time, as a number of minutes past trade 
  opening time, which was 9:30am local time.
- The values are the price of Apple stock at that time, in dollars.

For example, the stock cost 0 at 10:30am, 
so stock_prices_yesterday[60] = 500.

建议的暴力解决方案是：

 The brute force ↴ approach would be to try every pair of times
 (treating the earlier time as the buy time and the later time as the 
 sell time) and see which one is best. There are n2 such combinations,
 so this will take O(n2) time.

我不知道这个解决方案是 O(n2)。

如果我有一个包含股票价格的小列表，比如 [21,10,43]，那么所有可能的组合将是：

(21, 10)
(21, 43)
(10, 43)
(10, 21)
(43, 10)
(43, 21)

这不是 n**2 组合......我相信这真的很简单，但它总能打动我。

Answer 1

That is not n**2 combinations

Big-O符号是最重要的因素，组合的数量，不包括重复（例如（10, 10））仍然与[=18成正比=]n²。事实上，没有重复的组合总数是 n²-n。在 big-O 你只保留最重要的术语，所以 O(n²).

通常会通过

枚举成对集合

for i in indexes
  for j in indexes
    if i != j then
      process(i, j)

再次为每个索引枚举所有索引：索引数乘以索引数：O(n²).

蛮力解决方案的大 O 符号

Big O notation for brute force solution

big-o

asymptotic-complexity