网站建设价格标准方案,c2c代表平台有哪些,网站建设公司专业开发北京网站,小程序开发问题均摊时间复杂度#xff0c;它对应的分析方法#xff0c;摊还分析#xff08;或者叫平摊分析#xff09;
均摊时间复杂度应用的场景比它更加特殊、更加有限 // array表示一个长度为n的数组// 代码中的array.length就等于nint[] array new int[n];int count 0;void insert…均摊时间复杂度它对应的分析方法摊还分析或者叫平摊分析
均摊时间复杂度应用的场景比它更加特殊、更加有限 // array表示一个长度为n的数组// 代码中的array.length就等于nint[] array new int[n];int count 0;void insert(int val) {if (count array.length) {int sum 0;for (int i 0; i array.length; i) {sum sum array[i];}array[0] sum;count 1;}array[count] val;count;}
这段代码实现了一个往数组中插入数据的功能。当数组满了之后也就是代码中的 count array.length 时我们用 for 循环遍历数组求和并清空数组将求和之后的 sum 值放到数组的第一个位置然后再将新的数据插入。但如果数组一开始就有空闲空间则直接将数据插入数组。 先分析上述代码的时间复杂度
最理想的情况下数组中有空闲空间我们只需要将数据插入到数组下标为 count 的位置就可以了所以最好情况时间复杂度为 O(1)。最坏的情况下数组中没有空闲空间了我们需要先做一次数组的遍历求和然后再将数据插入所以最坏情况时间复杂度为 O(n)。
平均时间复杂度是多少呢答案是 O(1)
假设数组的长度是 n根据数据插入的位置的不同我们可以分为 n 种情况每种情况的时间复杂度是 O(1)。除此之外还有一种“额外”的情况就是在数组没有空闲空间时插入一个数据这个时候的时间复杂度是 O(n)。而且这 n1 种情况发生的概率一样都是 1/(n1)。所以根据加权平均的计算方法我们求得的平均时间复杂度就是 上述的分析过于复杂
可以使用摊还分析法通过摊还分析得到的时间复杂度我们起了一个名字叫均摊时间复杂度。
每一次 O(n) 的插入操作都会跟着 n-1 次 O(1) 的插入操作所以把耗时多的那次操作均摊到接下来的 n-1 次耗时少的操作上均摊下来这一组连续的操作的均摊时间复杂度就是 O(1)。这就是均摊分析的大致思路。
听起来很复杂但是均摊时间复杂度就是一种特殊的平均时间复杂度我们没必要花太多精力去区分它们。你最应该掌握的是它的分析方法摊还分析。至于分析出来的结果是叫平均还是叫均摊这只是个说法并不重要。 此文章为5月Day6学习笔记内容来源于极客时间《数据结构与算法之美》
