为了描述一个算法的效率,就用到了这个大O,包括:
O(n) 线性时间操作
O(1) 常数时间操作
O(log n) 对数时间操作
例如在 Redis 的文档中,对每个命令都会给出复杂度描述
?
?...明白大O的作用有助于我们提高程序的效率,下面看看他们的具体含义
O(n) 线性时间操作
假设有一个盒子,其中有多个印着数字的卡片(例如 1, 2, 3, 4, … 16)
现在我们被要求找出数字6的卡片...(1, 2, 3, 4, … 16),在盒子外面写上盒子中有16个数字
当有人问我们盒子里有多少个数字的时候,我们看一眼盒子上的标记就可以马上告诉他有16个
这就是常数操作,记为 O(1)
O(log...n) 对数时间操作
假设有一个盒子,其中有数字(1, 2, 3, 4, … 16),并且这些数字是排好序的
当有人要求找到数字16,以为有序,我们可以把这些数字分成两组,对符合范围的那个组继续拆开,这样...很不错
知道了大O的含义,我们也就可以更好的选择算法,例如 redis 中的 keys命令,他的复杂度是 O(n),我们就要慎用了