我在数据库中存储了一对变量及其相关值的列表。
var1 var2 corr
我的算法涉及按降序对列表进行排序(基于相关值)，然后检索前 k 对。
这个算法的时间复杂度是多少？这取决于我如何排序吗？我正在使用 ORDER BY 子句使用 sql 查询对列表进行排序。
最佳答案
SQL 数据库管理多级内存——基本上是内存中的数据页和磁盘上的存储。传统的复杂性度量并不能很好地捕获 SQL 查询的性能特征。为此，您需要了解执行计划、底层算法以及相对于可用资源的数据大小。
我的下一个 react 是:如果你需要对数据进行排序，那就对数据进行排序。时间复杂度与它有什么关系？也就是说，您还有哪些其他选择？
通常，数据库中实现的排序具有 O(n log(n)) 的复杂度。但是，实际速度在很大程度上取决于其他因素。列上的索引降低了复杂性。适合内存的数据传输速度更快。适合单个页面的数据可能会更快。
我不确定您所说的“这取决于我如何排序吗？”是什么意思。在 SQL 中只有一种表达排序的方法，即使用 order by 子句，而且它没有太多选项。按 asc 排序与按 desc 排序对性能没有影响或影响很小。
关于sql - 按降序对列表进行排序的时间复杂度。，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/25066008/