算法笔记

求解同一个问题,可以有许多不同的算法,那么,怎样衡量这些算法的优劣呢？ 首要的条件是选用的算法必须是正确的,其次则应考虑以下三个方面:

1. 执行算法所耗费的时间
2. 执行算法所占用的内存开销(主要考虑占用的辅助存储空间)
3. 算法应易于理解,易于编码,易于调试

时间复杂度

• 语句频度指该语句在一个算法中重复执行的次数,一个算法的时间耗费是该算法中所有语句频度之和
• 如果算法的执行时间T(n)与问题规模n无关,是一个常数,则记做T(n)=O(1)
• 数据结构中常用的时间复杂度频率计数有以下7种 `
  1. O(1) 表示常数型
  2. O(n) 表示线性型
  3. O(n^2) 表示平方型
  4. O(n^3) 表示立方型
  5. O(2^n) 表示指数型
  6. O(log2n) 表示对数型
  7. O(nlog2n) 表示二维型 `

空间复杂度

常见排序算法

1. 冒泡排序(Bubble Sort),它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。 走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。最大比较次数n(n-1)/2,最大移动次数3n(n-1)/2 其时间复杂度为O(n^2)
2. 快速排序(Quick Sort),是对冒泡排序的一种改进,快速排序采用的是分治策略，是目前最快的排序算法。 快速排序的基本思想是通过一趟排序将待排序记录区分成两个独立的部分，其中一部分的关键字均小于等于另一部分的关键字。 再分别对这两部分进行下一趟排序，最后使整个记录有序。平均时间复杂度为O(nlog2n),在n较大时，快速排序是目前认为最好的一种内部排序方法
3. 直接插入排序,每次将一个待排序的记录，按照其关键字插入到已经排好的记录序列中的适当位置
4. 简单选择排序,每次从待排无序记录中选出关键字最小的记录插入到已排好序的记录序列的后面