朗读

算法笔记(1)

文章目录[x]
  1. 1:前言
  2. 2:算法时间复杂度
  3. 3:实验测试复杂度
  4. 4:常见的十种排序方式及其稳定性

时间复杂度

  • 前言

时间复杂度和空间复杂度在程序中经常是我们需要考虑的问题。下面小生列举一个例子,以便更直接的认识时间复杂度。

我们知道一个电脑的性能是取决于CPU和GPU的。先假设现在的主流计算机的计算能力是每秒一亿次即10的8次方。

时间复杂度 1s可以运行的次数
线性阶(n) 一亿次
平方阶(n的平方) 10000次
指数阶(2的n次方) 大约27次
对数阶(log2n) 可以运行2的一亿次方

 

由上一个表格可以看出算法的优化是一个很重要的东西比如你把一个n的平方的算法优化到nlogn提升的就不是一点两点。因为一个程序如果你几年都得不到一个结果,很多时候程序就没有任何的意义。

  • 算法时间复杂度

下面给常见的时间复杂度一个快慢的排序(从上至下依次变快)

阶乘(n!) 最慢
2的n次方 超慢
n的平方、n的立方 慢(n的平方,如冒泡排序、插入排序、选择排序)
nlogn 及格算法(归并、快速排序)
n 比较优秀算法
sprt(n) 比较
logn 优秀算法(如二分查找)
  • 实验测试复杂度

这里我用java以汉诺塔为例大致测试一下(也可以测测电脑的运算速度)

汉诺塔的时间复杂度是n的平方

 

import javax.print.attribute.standard.MediaName;

public class TowerOfHanoi {

public static void main(String[] args) {

long now = System.currentTimeMillis();
long num1 = Runtime.getRuntime().freeMemory();
printHanoiTower(20, "A", "B", "C");
long end = System.currentTimeMillis();
long num2 = Runtime.getRuntime().freeMemory();
System.out.println("所用时间:"+(end-now)+"ms");
System.out.println("所用空间:"+(num1-num2));
}

static void printHanoiTower(int N, String from,String to, String help) {

if (N==1) {
System.out.println("move"+N+"from"+from+"to"+to);
return;
}

printHanoiTower(N-1, from, help, to);
System.out.println("move"+N+"from"+from+"to"+to);
printHanoiTower(N-1, help, to, from);

}

}

这里我的N传的是20,看一下结果

当我把n改为22运行一下

会发现时间相差的还是比较大的。

  • 常见的十种排序方式及其稳定性

此图来自百度图片。

这里的稳定性是指两个相同的数字如果排序后位置未变则表示该算法稳定。其中希尔排序一般不用,时间复杂度大约在n的1.3次方左右。

 

 

 

点赞

发表评论

昵称和uid可以选填一个,填邮箱必填(留言回复后将会发邮件给你)
tips:输入uid可以快速获得你的昵称和头像

Title - Artist
0:00