SQL Server与MySQL/PHP和BIG O

Question

一位同事向我提到，SQL Server不适用于Big O，因为它与MySQL/PHP一样。

凡是需要CPU时间有一个大O ...

难道我被误解的东西？我的意思是如果查询运行，总会有一个大O？ SQL Server如何可以除外或不同？

Answer 1

大O表示法只是一种根据操作的数据大小来确定算法运行时间的方法。例如，快速排序的平均运行时间为O（n log n）。但是，它可能有最坏情况的O（n^2），并且在O（log n）处运行的优化版本存在（就地）。数据库服务器需要执行的每个操作和查询（即算法）都会有相应的运行时间，可以用Big O符号表示。

对于数据库，例如，SELECT查询通常是O（n），并且可以是O（log n）并且索引存在。不管这是MySQL还是Oracle或MS SQL。

我相信MS SQL在SQL Server Management Studio中有一个名为Estimated Execution Plan的工具，可以帮助您查找执行时间。

总之，似乎你的故事的细节丢失，或有人明白了什么错误。

Answer 2

你应该和你的同事谈谈他们的意思。

“大O”是指算法在输入大小方面的时间复杂度。 （See这里是关于该主题的讨论。）“大O”估计本身是时间复杂度的上限。

时间复杂度是算法的一个特征。运行SQL查询的代码实现该查询的算法。因此，该查询将具有与其相关的一些时间复杂性度量。这将适用于所有数据库。