Java学习笔记11

算法中的时间频度与时间复杂度

时间频度

一个算法花费的时间与算法中语句的执行次数成正比例,哪个算法中语句执行次数多,它花费时间就多。一个算法中的语句执行次数称为语句频度或时间频度。记为T(n)

时间复杂度

一般情况下,算法中的基本操作语句的重复执行次数是问题规模 n 的某个函数,用 T(n)表示,若有某个辅助函数 f(n),使得当 n 趋近于无穷大时,T(n) / f(n) 的极限值为不等于零的常数,则称 f(n)是 T(n)的同数量级函数。记T(n)=O( f(n) ),称O( f(n) ) 为算法的渐进时间复杂度,简称时间复杂度;

T(n) 不同,但时间复杂度可能相同。 如:T(n)=n²+7n+6 与 T(n)=3n²+2n+2 它们的 T(n) 不同,但时间复杂
度相同,都为 O(n²)

计算时间复杂度的方法:

  1. 用常数 1 代替运行时间中的所有加法常数 T(n)=n²+7n+6 => T(n)=n²+7n+1

  2. 修改后的运行次数函数中,只保留最高阶项 T(n)=n²+7n+1 => T(n) = n²

  3. 去除最高阶项的系数 T(n) = n² => T(n) = n² => O(n²)

常见的时间复杂度

常数阶 O(1) 对数阶 O(log2n) 线性阶 O(n) 线性对数阶 O(nlog2n) 平方阶 O(n^2) 立方阶 O(n^3) k 次方阶 O(n^k) 指数阶 O(2^n) 

常见的算法时间复杂度由小到大依次为:
Ο(1)<Ο(log2n)<Ο(n)<Ο(nlog2n)<Ο(n2)<Ο(n3)< Ο(nk) <Ο(2n)
随着问题规模 n 的不断增大,上述时间复杂度不断增大,算法的执行效率越低;

我们应该尽可能避免使用指数阶的算法

StringBuffer和StringBuilder

前面所学习的string类是不可变的字符序列,而StringBuffer和StringBuilder非常类似,均代表可变的字符序列;

StringBuffer 线程安全,做线程同步检查, 效率较低;
StringBuilder线程不安全,不做线程同步检查,因此效率较高;

在平时的项目中一般采用高效率的StringBuilder类

String Builder常用方法

重载的public StringBuilder append(…)方法
可以为该StringBuilder 对象添加字符序列,仍然返回自身对象

方法 public StringBuilder delete(int start,int end)
可以删除从start开始到end-1为止的一段字符序列,仍然返回自身对象

方法 public StringBuilder deleteCharAt(int index)
移除此序列指定位置上的 char,仍然返回自身对象

重载的public StringBuilder insert(…)方法
可以为该StringBuilder 对象在指定位置插入字符序列,仍然返回自身对象

方法 public StringBuilder reverse()
用于将字符序列逆序,仍然返回自身对象

方法 public String toString()
返回此序列中数据的字符串表示形式;

值得注意的是:

当我们需要对一个字符串追加序列时一般采用append方法用来减少内存的使用和提高运行效率;

版权声明:玥玥 发表于 2021-04-04 1:18:39。
转载请注明:Java学习笔记11 | 女黑客导航