算法的复杂性能和空间

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

真实世界：
在现实世界中的应用程序 - 我们关心的不仅是理论上的空间/时间复杂性，而且关于常量（一个算法占用一半的时间尽管他们可以处于相同的复杂等级，但我作为另一个人更好。这是因为复杂类忽略了常量。）。
我们还考虑了程序/算法的实现时间和可维护性。