算法複雜度：如何查看「功耗」作爲參數？

空間和時間被認爲是分析算法複雜性的晴雨表。但是現在，隨着移動設備上GPU的出現，有許多可能的應用程序可以使用這種高性能在移動設備上運行復雜的算法。例如：iOS的Metal框架可用於GPGPU操作。但不用說，它消耗了大量的力量。所以，我的問題是，如果我正在移動設備上開發/實現圖表搜索算法，那麼我是否也應該考慮算法和時空的「功耗」複雜性？現在，我知道這個論點可能是權力是算法不會直接消耗的，我完全同意這一點。所以，也許我的語法在說權力是度量算法效率的另一個維度時是不正確的。但是不應該將權力視爲算法的性能指標？算法複雜度：如何查看「功耗」作爲參數？

來源

2015-09-28 Kunal Shrivastava

我不知道能源消耗的任何形式化的，但時間和空間都可能對能源比較有用的代理：更少的CPU週期需要更少的能量，和更少的內存訪問做的一樣好。關於設計用於最小化完成特定任務的能量消耗的算法概述，參見例如[here]（http://cacm.acm.org/magazines/2010/5/87271-energy-efficient-algorithms/fulltext），其中提到[this other survey]（http://people.cs.pitt.edu /〜kirk/cs3150spring2010/sigactreview.pdf）。 –

有趣的想法。我認爲在大O的意義上，功耗可以衡量爲隨着時間的推移內存使用量的積分，記住需要一些非零的「內存」（至少一個指令指針寄存器）只是爲了保持CPU運行在一個無所作爲的循環。對於許多算法，您只需乘以最壞情況的時間和內存要求，但該框架將適當地獎勵花費大量內存短時間使用的算法，但大部分時間花費很少。 –

感謝您的回覆。我覺得，根據你的回答，存儲器訪問次數可以被認爲與功耗成正比。事實上，如果這個事實被認爲是論證的前提，那麼我必須更仔細地看待空間複雜性。這意味着我不能只考慮使用的淨空間，但我還必須考慮內存分配和釋放的次數。 –

爲了使這成爲可能，你需要的能源消耗的模式，你可以涉及到的原子操作在你的算法。

像「乘法消耗能量中的一個單位」和「存儲器插槽使用能量的兩個單元每單位時間」。也許關係能量=時間x空間可能是有道理的。

無論如何，這樣一個「天真」的模型可能會遭受與時間複雜度模型相同的現象：它不會與現代架構的行爲產生任何相似性，並且可能會出現數量級錯誤。

使用更準確的模型將是棘手的分析。

來源

2015-09-28 13:07:35

能量=時間x空間是一個很好的第一個裂縫。更精確的模型*可以同時易於處理和現實 - 看看Aggarwal等人的I/O複雜性模型的成功。用於建模具有2個不同級別內存的系統。 –

@j_random_hacker：我寧願相信精緻的模型既不易處理也不現實，但這僅僅是一個觀點:) –

號複雜性解釋了時間/內存如何算法尺度。權力將是時間和記憶的功能。

假設有算法A - O（N^2）和B - O（N^3），他們都解決了同樣的問題。對於n = 1000，B使用1個單位的電力，而A使用20個。現在，當你擴展到n = 10k時，B將需要1000個單位的電力，而A將僅需要2000個。在n = 100k時，B需要1'000' 000，而A需要200'000。等等。這假定執行該算法的能量消耗是恆定的。

順便說一句，同樣的事情發生的時間。例如對於短陣列，沒有什麼比線性搜索更勝一籌。

對於一個特定的情況下（渲染上固定的分辨率UI）是有意義的測量的功率使用和優化它。但是，今天對決議有用的東西明天不一定是正確的。

來源

2015-09-28 13:07:51 Sorin

「這假設能耗是恆定的執行算法。」 - 對典型的現代CPU來說可能是一個合理的假設，但總功耗成本中必須有一個與正在使用的內存字節數成正比的項。例如。使用O（1）字節內存的O（n）算法必須使用比使用O（n）字節內存的O（n）算法漸近更少的功率。 –

算法複雜度：如何查看「功耗」作爲參數？

回答

相關問題