最佳渐近符号
Best asymptotic notation
如果一个算法最坏情况运行时间是6n^4 + 2，它最好情况运行时间是67+6n^3。什么是最合适的渐近符号。
我正在尝试学习大 O 表示法。
是 Θ(n^2) 吗？
本质上，Big-Oh 时间复杂度分析是针对最佳情况、最坏情况或算法执行的平均操作数定义的。 “是 Θ(n^2) 吗？”那么，您应该指定要查找的案例？或者你的意思是说所有情况下都是 Θ(n^2) 吗？ （这显然是不正确的）
话虽如此，我们知道算法在最坏的情况下会执行 6n^4 + 2 操作。所以它有 Θ(n^4) 最坏情况的复杂性。我在这里使用了 theta，因为我确切地知道要执行多少操作。在最好的情况下，它执行 67+ 6n^3 操作。所以它在最佳情况下具有 Θ(n^3) 时间复杂度。
平均时间复杂度如何？好吧，只要我没有提供输入的概率分布，我就不知道。可能 best-case-like 场景很少发生，平均时间复杂度为 Θ(n^4)，反之亦然。因此，只要我们没有提供输入概率分布、算法本身或递归关系，我们就不能直接从 worst/best 个案例时间复杂度中推断出平均时间复杂度。 （好吧，如果最佳和最差时间复杂度相同，那么我们当然可以得出平均时间复杂度等于它们）
如果提供算法，我们可以计算平均时间复杂度，对输入做出一些非常基本的假设（如等概率分布等）。例如在线性搜索中，最好的情况是 O(1)。最坏的情况是 O(n)。假设等概率分布，您可以使用期望公式得出平均时间复杂度为 O(n) 的结论。 [（输入 i 的概率）*（该输入的操作次数）]
最后，您的平均时间复杂度不能是 Θ(n^2)，因为您的最佳和最差时间复杂度比二次方差。等待这个算法平均执行 n^2 次操作是没有意义的，而它在最好的情况下执行 n^3 次操作。
最好情况的时间复杂度 <= 平均时间复杂度 <= 最坏情况的时间复杂度
如果一个算法最坏情况运行时间是6n^4 + 2，它最好情况运行时间是67+6n^3。什么是最合适的渐近符号。
我正在尝试学习大 O 表示法。
是 Θ(n^2) 吗？
本质上，Big-Oh 时间复杂度分析是针对最佳情况、最坏情况或算法执行的平均操作数定义的。 “是 Θ(n^2) 吗？”那么，您应该指定要查找的案例？或者你的意思是说所有情况下都是 Θ(n^2) 吗？ （这显然是不正确的）
话虽如此，我们知道算法在最坏的情况下会执行 6n^4 + 2 操作。所以它有 Θ(n^4) 最坏情况的复杂性。我在这里使用了 theta，因为我确切地知道要执行多少操作。在最好的情况下，它执行 67+ 6n^3 操作。所以它在最佳情况下具有 Θ(n^3) 时间复杂度。
平均时间复杂度如何？好吧，只要我没有提供输入的概率分布，我就不知道。可能 best-case-like 场景很少发生，平均时间复杂度为 Θ(n^4)，反之亦然。因此，只要我们没有提供输入概率分布、算法本身或递归关系，我们就不能直接从 worst/best 个案例时间复杂度中推断出平均时间复杂度。 （好吧，如果最佳和最差时间复杂度相同，那么我们当然可以得出平均时间复杂度等于它们）
如果提供算法，我们可以计算平均时间复杂度，对输入做出一些非常基本的假设（如等概率分布等）。例如在线性搜索中，最好的情况是 O(1)。最坏的情况是 O(n)。假设等概率分布，您可以使用期望公式得出平均时间复杂度为 O(n) 的结论。 [（输入 i 的概率）*（该输入的操作次数）]
最后，您的平均时间复杂度不能是 Θ(n^2)，因为您的最佳和最差时间复杂度比二次方差。等待这个算法平均执行 n^2 次操作是没有意义的，而它在最好的情况下执行 n^3 次操作。
最好情况的时间复杂度 <= 平均时间复杂度 <= 最坏情况的时间复杂度