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方法如何工作，以及使用這些方法在數組中查找最小或最大值時的時間複雜度是多少？