按降序排序列表的时间复杂性。

Question

我有一对变量的列表以及它们的相关值存储在数据库中。

var1  var2  corr  

我的算法包括按降序(基于相关值)对列表排序，然后检索顶k对。

这个算法的时间复杂度是多少？这取决于我是如何分类的吗？我使用ORDER子句使用sql查询对列表进行排序。

Answer 1

SQL数据库管理多级内存--基本上是内存中的数据页和磁盘上的存储。传统的复杂性度量不能很好地捕获SQL查询的性能特征。为此，您需要了解执行计划、底层算法以及相对于可用资源的数据大小。

我的下一个反应是:如果您需要对数据进行排序，那么对数据进行排序。时间的复杂性和它有什么关系？也就是说，你还有其他选择吗？

通常，在数据库中实现的排序将具有O(n (N))复杂性。然而，实际速度在很大程度上取决于其他因素。列上的索引降低了复杂性。存储在内存中的数据速度更快。适合于单一页面的数据可能会更快。

我不明白你所说的“这取决于我是如何分类的吗？”在SQL中只有一种表达顺序的方法，使用order by子句，而且它没有太多的选项。asc与desc的排序对性能没有或最小的影响。