ruby 的 .min 和 .max 方法如何工作，使用这些方法在数组中查找最小值或最大值时的时间复杂度是多少？

Question

上下文：

我正在研究一个算法问题，以便在给定一系列股票价格时确定 max_stock_profit。我试图确定所述方法的时间复杂度，并遇到了在 each 方法中的数组上使用的 .min 。这让我提出了标题为 post.

的问题

一般来说，当简单地查看长度为 1,000,000 的数组上的 .min 或 .max 方法时，运行宁 .min 或 .max 在数组上需要线性时间 O(n) 来确定最小值或最大值，其中 n 是数组的长度？..

如果是这样，那么根据下面显示的示例代码，通过运行ning .min 或 .max 方法在 each 方法中，不会是时候复杂度为 O(n^2)，因为它需要运行在 each 方法中进行另一次迭代以确定最小值？我认为代码片段应该在 O(n) 时间运行ning，但我对 .min 和 .max 的工作原理缺乏理解，这是造成极大混乱的原因。

是否因为 .min 是在仅包含 2 个值的数组上调用的，所以可以假设代码行以恒定时间 O(1) 运行？任何帮助消除我对正在发生的事情的误解的帮助将不胜感激。谢谢。

示例代码片段：

stock_prices = [5, 7, 2 ,4, 9, 1, 8]
min_price = stock_prices[0]
max_profit = 0

stock_prices.each do |current_price|
    min_price = [min_price, current_price].min
    potential_profit = current_price - min_price  
    max_profit = [max_profit, potential_profit].max
end

Answer 1

each 中的 .min 和 .max 操作应用于只有 2 个元素的数组，因此每个都是 O(1) 操作。改变 n，stock_prices 中的元素数量，不会改变每次迭代中找到 .min 或 .max 的时间量，它们与 n 无关。因此，整个块是 O(n).

ruby 的 .min 和 .max 方法如何工作，使用这些方法在数组中查找最小值或最大值时的时间复杂度是多少？

How does ruby's .min and .max method work, and what is the time complexity when using those methods to find min or max value in an array?

ruby

arrays

max

min

time-complexity