1:最好为最快情况下的时间复杂度;
2:最坏为最慢情况下的时间复杂度;
3:平均复杂度:每种情况发生的概率相加(注意该概率要先乘以该概率发生的概率)
4:平摊时间复杂度:特殊的平均复杂度,在有规律的情况下,进行复杂度的平摊。
前n个操作复杂度都是O(1),第n+1次操作的复杂度是O(n),所以把最后一次的复杂度分摊到前n次上,那么均摊下来每次操作的复杂度为O(1)
1:最好为最快情况下的时间复杂度;
2:最坏为最慢情况下的时间复杂度;
3:平均复杂度:每种情况发生的概率相加(注意该概率要先乘以该概率发生的概率)
4:平摊时间复杂度:特殊的平均复杂度,在有规律的情况下,进行复杂度的平摊。
前n个操作复杂度都是O(1),第n+1次操作的复杂度是O(n),所以把最后一次的复杂度分摊到前n次上,那么均摊下来每次操作的复杂度为O(1)
本文标题:四:最好复杂度,最坏复杂度,平时复杂度(期望平均复杂度\加权平均
本文链接:https://www.haomeiwen.com/subject/csfewktx.html
网友评论