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

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

我在查看一个算法问题，以确定max_stock_profit当给定的股票价格数组。我试图确定所述方法的时间复杂度，并遇到each方法内的阵列上使用的.min。这导致我问这个帖子中题为问题。

一般来说，当简单地查看.min或.max方法长度1,000,000例如在阵列上，也不会在运行阵列上.min或.max需要线性时间为O（n），以确定一个最小或最大值，其中n是数组的长度？

如果是这样，那么根据下面显示的示例代码，通过在each方法中运行.min或.max方法，时间复杂度不会是O（n^2 ），因为它需要在each方法中运行另一次迭代以确定最小值？我认为代码段应该在O（n）时间运行，但是我对.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

来源

2017-10-11 George.

正在做什么等''？这可能与为什么写这个人的人不只是说'min_price = stock_prices.min'有关。例如，也许这是一个连续的过程，逻辑是以迄今为止看到的最低股价为前提。 – pjs

是的，这是一个连续的过程，并且在比较最初的最低价格和当前价格时基于最低的股票价格。但是我对这段代码片段的时间复杂性感到困惑，特别是在.each方法中实现.min和.max时。我想通过使用.min，它需要在.each中进行另一次迭代，这导致我相信时间复杂度比O（n）花费的时间更长？ –

我相信这里的代码是O（n），也就是说它是基于股票价格的长度的线性关系 – stujo

在each的.min和.max操作正被应用于只有2元件阵列，所以每个是O（1）的操作。更改n（stock_prices中的元素数）不会改变在每次迭代中查找.min或.max的时间量，它们独立于n。因此，整个块是O（n）。

来源

2017-10-11 21:34:32 pjs

好的，谢谢你的回答。一般来说，如果数组较大，比如说长度为1000，那么最小/最大方法将花费线性时间，因为它已遍历每个元素正确？我在问，因为如果我想优化运行时间，在宽松地在另一个迭代器中使用.min或max时，生病时必须更加小心。 –

'min'在数组*的大小*上是线性的。但！在这种情况下，'min'迭代的数组的大小由一个常量（原始示例中为2，假设中为1000）限定。 *每当一个函数被一个常数限定时，它就在O（1）中。（只需将它插入Big-Oh的定义中即可看到。）底线：在讨论时间复杂度作为n的函数时，要小心谨慎地定义“n”是什么。 –

@GeorgeV。不，因为它不是迭代原始数组。 'each'块创建的临时数组只包含2个元素，所以每次迭代的工作量与原始数组长度无关。 – pjs

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

回答

相关问题

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