算法的複雜性能和空間

Question

我做在我的算法複雜性類的研究，我需要知道，如果有一種算法任何其他複雜，我所知道的和研究的是2種 1是在大O複雜性是時間和性能等 2-是空間複雜度是記憶的複雜性， 做算法有任何其他種類的複雜性？算法是用我錯過的其他東西來衡量的嗎？

Answer 1

在漸近的算法的複雜性而言 - 對，算法（和問題）在空間和時間上被測量。

然而，有很多我能說些什麼。我會盡力解決一些問題：

空間/時間消耗是從分析的方法得出
有分析算法的4種常見方法，用於空間和時間。請記住，big-O是一組函數，但是如何導出函數？的複雜性的功能是根據分析的方法，該方法是（通常）以下之一得到：

• 最好的情況
• 平均情況
• 最壞情況
• Amortized Analysis

這些方法中的每一個都可以用於任何算法 - 並且結果不保證是相同的。例如，快速排序具有最差情況時間複雜度和O(nlogn)平均情況時間複雜度。

多臺套：
除了大O表示法，我們還可以使用其他符號來表示的複雜性。附加公共符號是（由使用的通用性）：

• 大西塔（Θ）
• 大歐米茄（Ω）
• 小O
• 小的ω（ω）

不與分析方法相混淆：每個大西塔/大O /符號的......可與任何分析方法配對（最壞情況/平均情況/ ...）
更多細節上大西塔，大O和差異打賭吐溫他們可以在this thread

複雜性理論中找到：
在理論"Complexity Theory"領域 - 我們分析問題，不算法。在這個領域，我們關心的一個問題可以多項式解決（即，如果輸入大小ñ，那麼問題就可以在ň一些力量解決），多項式驗證（給出可能的解決方案，檢查它是否正確）。但是，還有其他類。
常見的複雜性類是：

• NP
• P
• NP-Hard
• P Space

另外 - 我們有興趣，如果問題是可以解決的/可判定的。描述的問題有解常見的類別是：

• R
• RE
• 的CoRE

真實世界：
在現實世界中的應用程序 - 我們關心的不僅是理論上的空間/時間複雜性，而且關於常量（一個算法佔用一半的時間儘管他們可以處於相同的複雜等級，但我作爲另一個人更好。這是因爲複雜類忽略了常量。）。
我們還考慮了程序/算法的實現時間和可維護性。