按年被提到
20162016 · 2 次2026
算法与数据结构›经典算法与数据结构·arXiv:1605.08448 · cs.DS

Energy-Efficient Algorithms

Erik D. Demaine, Jayson Lynch, Geronimo J. Mirano, Nirvan Tyagi · 2016
开始阅读 ↗PDFalphaXiv 讨论
被提及 · 2 人首次 2016-05-30 · 最近 2016-11-04
2不同的人
2活跃月份
2讨论串
1被引(OpenAlex)
arXiv 摘要(候选层不写导读)

We initiate the systematic study of the energy complexity of algorithms (in addition to time and space complexity) based on Landauer's Principle in physics, which gives a lower bound on the amount of energy a system must dissipate if it destroys information. We propose energy-aware variations of three standard models of computation: circuit RAM, word RAM, and transdichotomous RAM. On top of these models, we build familiar high-level primitives such as control logic, memory allocation, and garbage collection with zero energy complexity and only constant-factor overheads in space and time complexity, enabling simple expression of energy-efficient algorithms. We analyze several classic algorithms in our models and develop low-energy variations: comparison sort, insertion sort, counting sort, breadth-first search, Bellman-Ford, Floyd-Warshall, matrix all-pairs shortest paths, AVL trees, binary heaps, and dynamic arrays. We explore the time/space/energy trade-off and develop several general techniques for analyzing algorithms and reducing their energy complexity. These results lay a theoretical foundation for a new field of semi-reversible computing and provide a new framework for the investigation of algorithms.

候选层:至少 2 个不同的人、在 2 个不同月份提到过,还没到主书架的 3 人 3 个月。没有做立场标注,所以只写“被提及”。

HN 书评

没有评论直接链到它;下面是它被提交的讨论串里回复最多的评论(不计入统计)

讨论串里没有 ≥100 字的评论,只有提交记录。

被提交为 story · 2 次