博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
算法 - 最好、最坏、平均复杂度
阅读量:5854 次
发布时间:2019-06-19

本文共 796 字,大约阅读时间需要 2 分钟。

注:本文仅为笔记。

最好、最坏时间复杂度

略,比较容易分析。

平均时间复杂度

需考虑概率来计算。

概率论中的加权平均值,也叫作期望值,所以平均时间复杂度的全称应该叫加权平均时间复杂度或者期望时间复杂度

均摊时间复杂度

均摊时间复杂度及对应的摊还分析法。

对一个数据结构进行一组连续操作中,大部分情况下时间复杂度都很低,只有个别情况下时间复杂度比较高,而且这些操作之间存在前后连贯的时序关系,这个时候,我们就可以将这一组操作放在一块儿分析,看是否能将较高时间复杂度那次操作的耗时,平摊到其他那些时间复杂度比较低的操作上。而且,在能够应用均摊时间复杂度分析的场合,一般均摊时间复杂度就等于最好情况时间复杂度。

// 全局变量,大小为 10 的数组 array,长度 len,下标 i。int array[] = new int[10]; int len = 10;int i = 0;// 往数组中添加一个元素void add(int element) {   if (i >= len) { // 数组空间不够了     // 重新申请一个 2 倍大小的数组空间     int new_array[] = new int[len*2];     // 把原来 array 数组中的数据依次 copy 到 new_array     for (int j = 0; j < len; ++j) {       new_array[j] = array[j];     }     // new_array 复制给 array,array 现在大小就是 2 倍 len 了     array = new_array;     len = 2 * len;   }   // 将 element 放到下标为 i 的位置,下标 i 加一   array[i] = element;   ++i;}

clipboard.png

转载地址:http://hupjx.baihongyu.com/

你可能感兴趣的文章
jdk源码之ConCurrentHashMap源码注释
查看>>
在 PowerPC 下安装 K8S
查看>>
笔记_网络单位换算
查看>>
SCDPM2012 R2实战一:基于SQL 2008 R2集群的SCDPM2012 R2的安装
查看>>
tomcat7 的server.xml 里面 Connector 配置官方说明
查看>>
安装Ruby2.0
查看>>
SQL SERVER中字段类型与C#数据类型的对应关系
查看>>
StringBuffer
查看>>
2017年6月8日 笔记
查看>>
vue.js component 学习手记
查看>>
保存对象、关系映射
查看>>
父页面与子页面的相互操作
查看>>
LVS_DR
查看>>
我的友情链接
查看>>
Java堆和栈的区别
查看>>
Linux lsof命令详解
查看>>
m3u8文件简介
查看>>
RHEL6 64位系统安装ORACLE 10g 64bit 数据库
查看>>
SVG path
查看>>
清除网络共享文件夹密码缓存
查看>>