这个符号被称为平均情况吗？

Question

有些书中说theta符号被称为平均情况,而其他人则说theta不是普通情况.如果θ不是平均情况那么所谓的算法平均情况呢？

Answer 1

O, ? 和 ？符号实际上与算法的最佳/平均/最坏情况无关。它们是表达函数渐近行为的方法，无论它们是什么。

f(n) = O(g(n)) 意味着 f 不会比 g 增长得更快。g 是一个上限，无论是否紧。

f(n) = ?(g(n)) 表示 f 的增长速度不会比 g 慢。g 是下限，无论是否紧。

f(n) = ?(g(n)) 意味着 f 增长与 g 一样快。g 是上界和下界的紧界。

那么，算法的最佳/平均/最差运行时间是元素数​​量的函数，通常有 O, ?, ? 表示。

在对特定算法的分析中，人们通常能够推导出最坏情况的 O 界限，无论是否严格。此外，通过更多的努力，平均时间会受到限制。通常你不在乎最好的时间。

然后在分析给定问题时（无论解决它的任何特定算法），有时可以建立运行时间的绝对下限，即 ? 绑定在最佳时间（紧或不紧）。平均时间的下限有时是可能的，但技术性很强。

Answer 2

你混淆了两个不同的概念.

的平均情况下的时间复杂性是运行时间上平均(在某些概率分布)所有可能的输入.因此,它是特定算法的输入大小的函数.

theta-notation只是描述两个函数之间某种关系的一种方式.特别是如果一个函数是另一个函数的big-Theta,这告诉我们一个函数的增长速度大约与另一个函数一样快.

您可以使用big-Theta表示法来描述平均情况的复杂性.但您也可以使用任何其他符号来达到此目的.

如果一个算法,比方说平均情况下的时间复杂度,3*n^2 - 5n + 13,那么这是事实,它的平均情况时间复杂度Theta(n^2),O(n^2)和O(n^3).在这三个中,Theta(n^2)是对其时间复杂度的最准确的描述(但当然不如准确的表达准确,在实践中几乎不可能得到;我们通常可以提供的只是一些界限).

总而言之,theta-notation(和所有其他渐近符号)允许您根据众所周知的函数来表征算法的平均情况运行时间(例如,它大致增长为n^2).