App 開發基礎講義

給初學者的應用程式開發基礎知識

資料結構和演算法

結構化程式設計 Structured programming

演算法的極限:計算理論

  • 推薦書: 電腦也搞不定, 天下文化
  • 不能計算的問題: 例如停機問題
  • 問題可以計算,但是算法耗費太多資源或時間(已知最佳解就是指數時間 O(2^N),而非多項式時間內),因此不切實際,只能用最佳化逼近解
    • 2^N 太恐怖了,當 N = 100 時,就比大霹靂以來的微秒數還要多
    • 這就作 NP 類型的問題
      • 例如河內塔步驟,假設有 N 個的環,那麼最佳解的移動步驟是 2^N - 1,原始版本和尚要移動 64 個環根本就不可能。其他像是西洋棋必勝策略也是 NP 類型問題
  • 已知有指數時間解,但是不確定有沒有更好的多項式時間解

補充閱讀

》回到頁首