從硬體到軟體的分離#
- 早期計算機中，哪些功能由硬體實現、哪些由程序控制，界線並不清晰
- 約翰·莫奇利（John Mauchly）和約翰·埃克特（J. Presper Eckert）研製的第一台電子計算機 ENIAC，本質上是一台專用計算機，每次改變用途都需要重新接線
- 馮·諾依曼發現了這個缺陷，促成了 EDVAC 的誕生——世界上第一台程序控制的通用電子計算機，也是今天所有計算機的鼻祖
- 馮·諾依曼體系結構將計算機分為軟硬體兩部分，確立了頂層設計的重要性
高德納與算法分析的誕生#
高德納（Donald Knuth）是奠定計算機算法分析基礎的人，被譽為「算法分析之父」。作者列舉了高德納的五大貢獻：
- 算法分析的鼻祖：提出了評估計算機算法的標準
- 《計算機程序設計藝術》：計算機科學領域的「聖經」，比爾·蓋茲稱之為優秀程序員的必讀書
- 最年輕的圖靈獎得主：35 歲（1973 年）獲獎
- TeX 排版軟體的發明者：至今仍是全球學術排版的標準，被稱為全世界錯誤（bug）最少的軟體
- 矽谷圖靈獎得主中最會編程的人：在編程比賽中總是用最慢的計算機獲得第一名，因為他追求算法在設計時就達到最佳
高德納的算法分析思想#
高德納的核心思想包括三個部分：
- 只考慮大數據量的情況：計算機的發明就是為了處理大量數據，因此比較算法時只需考慮數據量特別大（趨近於無窮大）的情況
- 區分常數因素與變化因素：決定算法快慢的因素分為不隨數據量變化的常數因素，以及隨數據量變化的因素。衡量算法好壞時，只需考慮後者
- 數量級的差異至關重要：兩種算法在複雜度上即使只差一點點，N 很大之後效率可能差出萬億倍
作者用芝麻、西瓜、火車、大山、地球的比喻來形容算法複雜度的數量級之差：複雜度函數中不受 N 影響的常數，哪怕是千百倍，都是芝麻級的東西；而數量級的差異才是西瓜面前的比較。
要點#
- 體系結構確立了軟體從計算機科學中分離出來的基礎
- 高德納的思想奠定了全世界計算機領域衡量算法的標準