算法分析——时间复杂度

时间复杂度

定义&意义

• 一行代码运行的时间*该行运行次数（对所有行执行次运算）
• 描述一个算法的快慢性能（假设在同样算力的计算机上，且没有其他任务消耗计算机任务的理想情况下）

标识

• 约定用T(N) 表示所有主要语句的运行时间 ，单位时间为单位
• 将T(N)近似后用O(f(N)) 表示，其中，f(N) ~ F(N)

计算方法

用一个例子简单说明

int a  = 10 ;
for(i =0 ; i < a ; i++){
System.out.println(i);
}

• 第一行执行一次 ；记n

• 第二行中 ，i = 0 执行一次, i < a 执行11次，10次符合条件，1次判断越界，i++ 执行10次；分别记作 n、11n、10n

• 第三行中，执行10次 ，记10n

• 由此T(N) = 1n+1n+11n+10n+10n
  显眼从数学上说是个一次函数，也就是说改程序段的时间复杂度是线性的，由此推知，当时嵌套的二重、三重ffor循环时，其复杂度应为平方级别，立方级别

• 当遇到较复杂的程序时，其运行时间取决于执行最频繁的语句（e.g.：三重for循环时间主要取决于最内层的语句）
  相当于说办事情要抓主要矛盾了哈哈

其他常见描述时间复杂的增长数量级&举例

推算和证明用到一点求极限和基础数学知识，不是本文讨论的重点，故只列出结果

• 常数级别
• 对数 ：典型的二分查找
• 线性对数 典型并归排序
• 指数级别（只在某些特殊问题上有讨论价值，不能用于解决大问题，太慢）