算法分析爲三元計算機vs其他基於二元，基於第四類爲基礎

Question

當我分析算法時，我突然問自己這個問題，如果我們有三元計算機的時間複雜性會更便宜？或者有沒有我們可以構建計算機的基礎，以便時間複雜性分析無關緊要？我在互聯網上找不到太多東西，但基於三元的計算機在給定相同資源的情況下可以更快地處理它。

我將不勝感激任何想法在這個質疑

Answer 1

• 沒有，幾乎所有的算法理論的複雜性將繼續留在大O表示法相同，因爲它們不依賴於數字表示：他們只要假設某些基本操作（如加法或乘法）需要O（1）個步驟。

• 出於實際考慮，也許一些處理base-3表示的非常狹窄的區域本身會得到線性提升。就像現在一樣，在一個整數中獲取設置位的數量在現代處理器中有它自己的快速指令（POPCNT），所以它可以被認爲是O（1）。

• 想了解一種新的計算技術如何破壞算法的複雜性，請閱讀quantum computers。