algorithm - 算法复杂度性能和空间

Question

我正在课堂上研究算法复杂性，我需要知道是否还有其他算法复杂性，我所知道和研究的是 2 种类型 1-是 BIG O 复杂性，即时间和性能以及其他 2 - 空间复杂度是内存复杂度吗，算法还有其他类型的复杂度吗？算法是用我想念的其他东西来衡量的吗？

Answer 1

就算法的渐近复杂度而言 - 是的，算法（和问题）是根据空间和时间来衡量的。

但是，我可以说的还有很多。我将尝试解决一些问题：

空间/时间消耗源于一种分析
方法 算法有 4 种常用的分析方法，用于空间和时间。请记住，big-O 是一组函数，但是如何导出函数呢？复杂度的函数是根据分析方法导出的，分析方法（通常）是以下之一：

• 最佳案例
• 平均情况
• 最坏的情况下
• 摊销分析

这些方法中的每一种都可以用于任何算法 - 并且不能保证结果是相同的。例如，快速排序具有O(n^2)最坏情况时间复杂度和O(nlogn)平均情况时间复杂度。

更多集：
除了大 O 符号，我们还使用其他符号来表示复杂度。其他常见的符号是（根据使用的共同性）：

• 大西塔 (Θ)
• 大欧米茄 (Ω)
• 小o
• 小欧米茄 (ω)

不要与分析方法混淆：每个 Big Theta/Big O/ 符号...都可以与任何分析方法配对（最坏情况/平均情况/...）
有关 Big Theta、Big O 和他们之间的区别可以在这个线程中找到

理论复杂性：
在理论“复杂性理论”领域——我们分析问题，而不是算法。在这个领域，我们关心一个问题是否可以多项式解决（也就是说，如果输入的大小为n，那么问题可以在n的某个幂中解决），验证多项式（给定一个可能的解决方案，检查它是否是正确的）。但是，还有其他类。
常见的复杂度类别有：

• NP
• 磷
• NP-硬
• P空间

此外 - 我们对问题是否可以解决/可决定感兴趣。用于描述问题可解决性的常见类别是：

• R
• 回覆
• 核

现实世界：
在现实世界的应用程序中——我们不仅关心理论空间/时间复杂度，还关心常数（一种算法花费一半时间的算法要好得多，即使它们可以属于同一复杂度等级。这是因为复杂性类忽略了常量。）。
我们还考虑了程序/算法的实施时间和可维护性。