Permalink
Switch branches/tags
Nothing to show
Find file Copy path
Fetching contributors…
Cannot retrieve contributors at this time
34 lines (23 sloc) 1.74 KB

缘起

  • 看了一下.one文件里是2016-12-04整理的这部分,但并没有什么内容。
  • 2017-10-03把这部分整理一下。

内容

11.1 时间复杂度

  • **语句频度:**算法中每条语句被执行的次数。for(i=0;i<n;i++) a+=1;a+=1就被执行了n次,所以 语句频度为n。
  • 渐近时间复杂度: 当表示问题规模的n值趋于无穷大时的时间复杂度,将其记做:T(n)=O(f(n)),其中T(n)和f(n)是同数量级的。
    • f(n)的取值通常用执行语句中语句频度最大的值的数量级来描述。
  • 常见时间复杂度的关系 常数<对数<多项式<指数
    • O(1)<O(log2n)<O(n)<O(nlog2n)<O(n平方)<O(n3方)<O(2的n方)<O(n!)<O(n的n方)

11.2 冒泡排序法

  • 核心是两层for()循环,所以时间复杂度是0(n平方)。

11.3 选择法排序

冒泡法排序和选择法排序分析过程 其实想知道这两者有什么区别,无非选择时测试了一个监察哨,少比较了次数。

11.4 快速排序

  • 对冒泡的改进。‘C.A.R.Hoare’在1962年提出。将数分为左右两个部分,其中一部分所有数据比另一部分的所有数据小;然后将分得的数据进行同样的划分,重复操作,直到所有数据有序为止。

11.5 归并排序

  • 将待排序部分分为两部分,对分得的两部分再进行归并,之后再对其进行合并,所以这也分为2路归并和多路归并。

11.6 顺序查找

11.7 二分查找

  • 要求所要查找的数据必须是有序序列。

收获

  • 内容就这么多,代码的实现,我先没管,准备把数据结构的部分代码链接到这部分来。