1樓：
假設你這個矩陣是個凸凹不平的面，那麼極值就是面和另外乙個平行平面相切的地方，梯度下降法就可以，二階偏導數為零即是極值點，但區域性最小值沒什麼意義，區域性到底多大，哪個區域性你又沒給出。
修改一下，O（N）時間只夠掃瞄常數條線，所以既然你說了，那肯定是打靶法，先打Ｎ/2個離散點，再判斷周圍九宮格，過濾重複幾次，向趨勢明顯的方向繼續打N/4，重複這個過程，N/8，N/16......總和極限接近於N，得到的是乙個概率性質的結論，比如說我有99.99%的把握認為此點最優。
這個過程也可以是每次取對數或其他收斂函式，目測和的極限小於N的，我不會算，有會算的知友幫分析一下。
前提是你這個平面得光滑連續，這種情況就難說
2樓：靳凱
記得很久以前做 motion estimation 的時候遇到過類似的問題。簡單講需要在乙個 MxN 的矩陣中匹配乙個極小值。
關於這個問題有太多方案了。比如TSO，DSO等幾何匹配模式，類似於選K個點，按最小K位置再次迭代。
或者採用PSO粒子群，蜂群，蟻群等方法。通過區域性個體解和群體解來優化求解路徑。
然而以上都是針對比較好的多峰情況，求解曲面較為光滑。如果是完全隨機的這種，區域性極小值似乎emmmm....
3樓：陳許旻
看了 @墨雨蕭軒 的回答後想到乙個演算法：
現在正中間畫一條橫線，找到橫線上最小的位置a。如果這個位置上下兩個位置都比它大，那麼它是區域性最小。否則上下至少有乙個比這個位置小。
把較大的半個矩陣捨棄，因為從a開始按 @墨雨蕭軒 的貪心找區域性最小值不會離開沒被捨棄的半個矩陣。
接著畫一條n/2長度的豎線，又把矩陣分成了兩半。找到橫線加豎線合起來最小的位置。用同樣的方式把最小不在的半個矩陣捨棄。
這樣操作下去每兩次畫的線長度會減半，畫的線總長度是O(n)的。
4樓：墨雨蕭軒
我本來想說的是：先隨機選乙個位置，然後每次移動到周圍4個位置裡最小的那個，直到達到區域性極小值。但是發現好像很容易被卡成O(N^2)。
（已經被cxm大佬解決了orz）
STL庫里的演算法時間複雜度和空間複雜度都是最佳的嗎？
Alinshans 肯定不都是最佳的。但肯定比99 的人寫的都要好。競賽中不一定要求時間複雜度最小，但是基本上 嚴格一點的 要求達到乙個級別。比如複雜度能O nlogn 的你不要搞O n STL中的演算法肯定能確保你能達到，如果你的寫法沒有問題，但死活超時了 卡常數 我覺得題目出得有問題。另，你知道...
資料結構中的時間複雜度和空間複雜度有沒有直接的關係？
1.在絕大多數情況下，演算法的時間複雜度不會低於空間複雜度 2.為什麼在一段時間內學習到的實現同樣目標演算法中，二者似乎矛盾對立？因為如果A演算法在時空上都優秀於B演算法，我覺得你不會去記B演算法就醬 不用很長各種各樣的論述，你記住幾點 其實只要記住最後一點就可以了 1，完成乙個既定目標的任意演算法...
演算法時間複雜度中的PSPACE,coNP complete,DP complete的含義。
A complete 的定義對於所有 class 都一樣,就是說 class A NP 中的所有問題都可以規約到某個特定問題 3 SAT 想看書去找 Sipser,或者 Arora Barak,或者 Goldreich,或者 Papadimitriou.至於 PSPACE 和 coNP,這兩個算常見...