04 | 复杂度分析(下):浅析最好、最坏、平均、均摊时间复杂度

上一节,我们讲了复杂度的大 O 表示法和几个分析技巧,还举了一些常见复杂度分析的例子,比如 O(1)、O(logn)、O(n)、O(nlogn) 复杂度分析。掌握了这些内容,对于复杂度分析这个知识点,你已经可以到及格线了。但是,我想你肯定不会满足于此。

今天我会继续给你讲四个复杂度分析方面的知识点,最好情况时间复杂度(best case time complexity)、最坏情况时间复杂度(worst case time complexity)、平均情况时间复杂度(average case time complexity)、均摊时间复杂度(amortized time complexity)。如果这几个概念你都能掌握,那对你来说,复杂度分析这部分内容就没什么大问题了。

……………………………………………………………………………………………………………………………………..

// n表示数组array的长度
int find(int[] array, int n, int x) {
int i = 0;
int pos = -1;
for (; i < n; ++i) {
if (array[i] == x) {
pos = i;
break;
}
}
return pos;
}

最好情况时间复杂度就如名字所示,如果数组的第一个数就是我们想要查找的树,就不用进行遍历查找剩下的N-1种情况了,这时候时间复杂度为O(1);如果最后一个数才是我们要查找的,也就是说需要遍历N次 时间复杂度为O(n);

顾名思义,最好情况时间复杂度就是,在最理想的情况下,执行这段代码的时间复杂度。就像我们刚刚讲到的,在最理想的情况下,要查找的变量 x 正好是数组的第一个元素,这个时候对应的时间复杂度就是最好情况时间复杂度。

最坏情况时间复杂度就是,在最糟糕的情况下,执行这段代码的时间复杂度。就像刚举的那个例子,如果数组中没有要查找的变量 x,我们需要把整个数组都遍历一遍才行,所以这种最糟糕情况下对应的时间复杂度就是最坏情况时间复杂度。

要查找的变量 x 在数组中的位置,有 n+1 种情况:在数组的 0~n-1 位置中和不在数组中。我们把每种情况下,查找需要遍历的元素个数累加起来,然后再除以 n+1,就可以得到需要遍历的元素个数的平均值,即:

刚这个公式简化之后,得到的平均时间复杂度就是 O(n)。

 

均摊时间复杂度

均摊时间复杂度就是一种特殊的平均时间复杂度

 

 

07.25

前天昨天去姥姥家了

依旧是以前的矛盾,中午和爸妈到姥姥家;姥姥打电话叫大舅妈来一起吃饭,但没叫二舅妈一家,妈妈就很生气,发了一会脾气。

这属于历史遗留问题了,姥姥偏向大儿子过于倾斜,造成的恶性循环,循环循环。

放在我妈的角度,我妈自然是偏向二舅妈一家,二舅妈头脑和眼光都比大舅妈强,而且教育出来的孩子都蛮不错的,我自然是最喜欢小表弟的,鬼精的头脑调皮可爱;也不是不喜欢表妹,总感觉这几年接触的不多加上青春期的隔阂与羞涩就更加疏远了

听到小表弟去辅导班的消息心理确实失落的,后来听到每天走读是挺开心的嘿嘿。现在家长都挺重教育的,表哥的两个儿子幼儿园就送到最好的一小幼儿园了,每天来回车程一小时,表弟表妹也被安排到很好的三中。

孩子们许久不见窜高了好多嘿嘿

和汪聊到一点 果然“好人”在感情上面是占劣势的