【原】算法A时间复杂度O(n²)，算法B时间复杂度为O(n³)，为什么选择算法B而不选算法A的6个理由?

半佛肉夹馍 2023-10-20 发布于河南

展开全文

题主已经想到一个，A算法的常数可能过大，相反B算法就会变得更可行，还有其他的理由么？

空间复杂度过大，空间换时间但目标机器空间不足。
数据量过小，效率更高的算法耗用时间相对更长。
如常数时间每次查询都需要1毫秒，而平方复杂度在数据量低于某个值时只需几十个纳秒，那么显然后者为好。
一个典型案例就是对quick sort算法的优化：
当数据分割到小于等于6个元素时改用复杂度高半级的冒泡排序，最终表现却比纯粹的quick sort更好。
另一个案例是哈希表，当数据量较小时二分法查找只需十几次访问，哈希表本身的哈希算法却可能需要执行很多条指令（当然现在因为内存速率和CPU严重不匹配，cache miss本身消耗的额外时间可能就足够执行哈希算法了，具体哪个更好用需要先做测试才能确定）。
时间消耗不稳定，如常数时间的哈希表在冲突发生时退化到链表，而对数复杂度的二分法稳定在对数复杂度。
那么对于实时系统，哈希表可能就是不可行的。
数据准备/维护代价过大。
比如一个对数查询效率的数据结构，插入新数据的消耗可能是指数复杂度。
精度不足。
如布隆过滤器效率O（1），但只能确认数据不在集合中。
而它报告数据存在时，数据却可能不在，也就是存在误判。
类似的，有很多效率极高的近似算法，在需要精确解时显然是不能用的。
无法满足可靠性要求。
比如如果某高效算法无法做到事务级可靠性（ACID）、或者在多线程场合表现极差，那么在可靠性不可忽略的场合自然不能使用。
对数据性质有苛刻要求。
比如基数排序效率可达O（N），但要求数据必须是有限位的数字、每位符号数目有限且每个数字位满足进位值类似的权值约束。