algorithm - Big-O:你怎么知道针对特定的时间复杂度应该给出什么样的算法？

Question

因此，当有人要求您提供 O(n) 或 O(nlogn) 算法来计算某些内容时，您怎么知道要回答什么？似乎能够回答这类问题的唯一方法是事先了解各种算法的时间复杂度，而不是当场思考一些东西。我的假设是否正确？

Answer 1

简单的情况是:

沿着列表迭代 - O(n)

单个二进制或树操作 - O(log n)(这意味着向树中插入 n 个元素是 n log n)

哈希表操作 - O(1)

NP 完全问题(在这里你需要一些经验来培养直觉)- 一般的指数时间(在实践中，对于许多问题，可以应用有效的启发式方法)

对于具有 E 边和 V 顶点的图，复杂度为 F(E,V)，具体取决于算法的性质和图的密度。 E+V 以获得良好的 DFS/BFS。

几乎每个算法都可以划分为上述(或类似)小块的集合。当 block 递归组合时，如A-includes-B，复杂度成倍增加，当 block 彼此跟随时，如A-then-B，复杂度为max(complexity A, complexity B)