Classical-Cipher
凱撒（移位）密碼的複雜度是“n * n！”嗎？
我們可以說任何要解密的移位密碼都需要一個複雜度為“
n * n!”的算法嗎？（其中n是可能值的數量。如果是英語，則為 26）。我與達到相關的推理
n * n!如下：以這個詞
BRAZIL為例。我們有 26 種可能性B，R, 24 forA, etc. ThusO(n!). We also can have this 26 times, B was A now, but is a G in the next time, thus 26 which isO(n)henceO(n * n!)` 有 25 種可能性。
你到底是怎麼得出這個公式的？
您可以通過計算應用所有密碼的結果來破解凱撒密碼 $ n-1 $ （即 25）可能轉移到密文並選擇一個有意義的。計算複雜度只是 $ \mathcal{O}(n) $ .
如果您想基於頻率分析自動執行該過程，您選擇最可能偏移的相關步驟可能會有 $ \mathcal{O}(n^2) $ 複雜性，但在實踐中，您可能只需考慮最常見字母的一小部分即可實現這一點。（對於英文字母表，E、T、A、I、O 和 N 就足夠了）。
如果你考慮任意排列，你有 $ \frac{n(n+1)}{2} $ 可能性。這意味著， $ O(n^2) $ 是大 O 表示法中的正確複雜性，但我不明白為什麼你需要它，如果你能提供結果作為精確的公式。
凱撒密碼只包含 $ n $ 可能性，因此顯然 $ O(n) $ .
無論如何，這不包括頻率分析之類的算法，它既適用於凱撒密碼，也適用於一般的簡單替換密碼。