Complexity
計算複雜度和時間複雜度有什麼區別？
計算複雜性似乎在密碼學論文中被大量使用。
我所指的時間複雜度來自計算複雜性理論。
這兩個是一回事嗎？
有許多不同的計算成本模型，其中時間（由某個時鐘測量）只是其中之一。
- 我們必須等待多少秒才能執行這個算法？$$ time, measured in seconds $$
- 執行這個算法需要多少 CPU 週期？$$ time, measured in CPU cycles $$
- 該算法使用多少位記憶體？$$ space $$
- 將該算法表示為邏輯電路需要多少個與非門？$$ NAND metric $$
- 程序描述中有多少位，它使用了多少位記憶體，假設一個位操作和一個記憶體引用都需要一個單位時間，執行需要多長時間？$$ RAM metric $$
- 執行這個算法需要多大的矽晶片，我們必須為它供電多長時間？$$ AT metric $$
- 執行這個算法需要多少焦耳的能量？$$ energy $$
- 執行這個算法需要多少日元？$$ pocketbook $$
這些問題中的每一個的答案可能是輸入大小或輸入本身的複雜函式。例如，快速排序的最壞情況 RAM 成本是輸入大小的二次多項式函式， $ an^2 + bn + c $ , 對於一些係數 $ a $ , $ b $ ， 和 $ c $ 這取決於我們如何編寫它，而在最佳輸入上，RAM 成本是 $ u n + v $ .
複雜性理論通常不關心係數 $ a $ , $ b $ ， 和 $ c $ 但隨著多項式的次數， $ O(n^2) $ 對比 $ O(n) $ ，或其他質量不同的增長曲線形狀，例如 $ O(2^n) $ , $ O(\log n) $ , $ O(A^{-1}(n)) $ 在哪裡 $ A(n) $ 是阿克曼函式等，在您考慮的任何成本模型中。
計算複雜度可以指任何成本模型；時間複雜度通常只是指基於時間的，例如堆排序的時間複雜度是 $ O(n \log n) $ 而空間複雜度為 $ O(n) $ ，假設記憶體訪問成本是恆定的，但在更現實的 AT 度量中，最知名的對長度進行排序的成本- $ n $ 數組 $ n $ -位數是 $ n^{1.5 + o(1)} = (n\sqrt n)^{o(1)} $ 部分原因是矽網格上的通信成本。
最後三個成本模型是研究密碼分析攻擊的真正重要的模型，因為它們與攻擊的現實經濟成本相關：AT 指標易於形式化和研究算法，是能源成本的良好代表，而能源成本基本上決定了錢包成本。