花花酱 LeetCode Input Size V.S. Time Complexity SP2

本期节目介绍了输入数据规模和时间复杂度上限的关系，可以通过数据规模推算使用算法的类型。

• < 10: O(n!) permutation
• < 15: O(2^n) combination
• < 50: O(n^4) DP
• < 200: O(n^3) DP, all pairs shortest path
• < 1,000: O(n^2) DP, all pairs, dense graph
• < 1,000,000: O(nlogn), sorting-based (greedy), heap, divide & conquer
• < 1,000,000: O(n), DP, graph traversal / topological sorting (V+E), tree traversal
• < INT_MAX: O(sqrt(n)), prime, square sum
• < INT_MAX: O(logn), binary search
• < INT_MAX: O(1) Math