知晓算法运行时间上界的缩放规律可解决哪些实际问题？

知晓O(n²)这类运行时间上界的缩放规律后，你可以直接解决以下几类高频实际问题：

• 预判业务场景下的超时风险
  不管是做算法竞赛、后端接口开发还是前端交互逻辑，都可以快速估算不同输入规模下的耗时上限。比如你测到O(n²)的算法在输入规模n=1000时耗时12ms，当业务预期输入规模会涨到5000时，耗时上限会变成原来的(5000/1000)²=25倍，也就是300ms，如果接口要求响应时间不得超过200ms，你不用写完整代码测试就能知道这个算法不符合要求，必须换更低复杂度的实现。
• 技术选型阶段快速淘汰不合理方案
  做功能方案对比时不需要挨个写demo跑性能测试，直接通过缩放规律就能筛掉不合适的选项。比如排序功能候选方案是冒泡排序（O(n²)）和快速排序（O(nlogn)），业务预期数据量会到10万条，计算可知两者的操作数规模差了近4个数量级，直接就能淘汰冒泡排序的方案，节省方案验证的时间。
• 离线任务的资源与调度规划
  跑大数据离线处理、机器学习训练这类长周期任务时，可以提前规划调度时间和服务器资源。比如测试时O(n²)的聚类算法处理10万条数据耗时3分钟，当要处理100万条数据时，耗时上限会涨到原来的100倍也就是300分钟，你可以提前决定是错峰调度任务，还是加机器做并行拆分，避免任务超时影响后续数据链路。
• 性能瓶颈快速定位
  线上服务出现性能故障时可以快速缩小排查范围。比如最近业务用户量涨了3倍，接口响应时间从20ms涨到了180ms，刚好是3²=9倍的缩放比例，你就能直接锁定接口中存在O(n²)复杂度的逻辑段，不用漫无目的地排查数据库、网络等其他组件的问题。
• 项目成本与报价评估
  给项目做成本核算或者给客户报开发方案时，可以快速权衡开发成本与服务器成本。比如实现某需求用O(n²)的算法开发只需要2天，但未来百万级数据量下需要每年10万的服务器成本；用O(nlogn)的算法开发需要7天，但每年服务器成本只需要5000元，你可以通过缩放规律算出两种方案的长期总成本，选出性价比最高的方案。

内容的提问来源于stack exchange，提问作者mathgeek