评估算法的最佳时间/内存复杂性有经验法则吗

Question

我在评估问题的复杂性时总是遇到问题。我通常试图找到一个O(n)解，但有时O(nlogn)甚至O(n^2)是最好的解。

我知道的一条"经验法则"是，如果你有一个排序的数组，你需要找到一些东西，它可能可以在O(logn)中完成。我也知道排序不能比O(nlogn)更快。没有经验的程序员可以遵循类似的规则吗？你知道问题的复杂性吗？

对我来说，最麻烦的是O(n^2)，尤其是当我在考试中承受压力，浪费时间试图找到更好的考试时。

我希望这不是一个过于宽泛和基于观点的问题。

谢谢！

Answer 1

基于非比较的排序需要O(n)时间。例如：基数排序。

这本书读起来不错。http://bigocheatsheet.com/它包含常见算法的列表，它们的空间和时间复杂性。希望这能有所帮助。