排序分类:
内部排序: 把数据加载到内存中进行排序, 适用于数据量小的情况.
外部排序: 借助外部的文件等, 数据量大, 无法加载到内存.
常见分类如图:
算法复杂度
算法复杂度分为时间复杂度和空间复杂度. 其作用: 时间复杂度时间复杂度是指执行算法所需要的计算工作量; 而空间复杂度是指执行这个算法所需要的内存空间. 算法的复杂性体运行该算法时的计算机所需资源的多少上, 计算机资源最重要的是时间和空间, 即寄存器资源, 因此复杂度分为时间和空间复杂度.
空间复杂度:
描述一个算法所需要的空间大小, 即占用的内部内存, 或者外部的内存大小, 目前的设备性能各方面发展较快, 空间复杂度已经不是影响程序性能的主要因素.
时间复杂度:
概述:
时间复杂度是一个函数, 它定性描述该算法的运行时间. 这是一个代表算法输入值的字符串的长度的函数. 时间复杂度常用大 O 符号表述, 不包括这个函数的低阶项和首项系数. 使用这种方式时, 时间复杂度可被称为是渐近的, 亦即考察输入值大小趋近无穷时的情况.
时间频度
一个语句执行次数称为语句频度或时间频度, 记为 T(n). 算法花费的时间与算法中语句的执行次数成正比例, 哪个算法中语句执行次数多, 它花费时间就多.
时间复杂度:
一般情况下, 算法中基本操作重复执行的次数是问题规模 n 的某个函数, 用 T(n) 表示, 若有某个辅助函数 f(n), 使得当 n 趋近于无穷大时, T(n)/f (n) 的极限值为不等于零的常数, 则称 f(n) 是 T(n) 的同数量级函数. 记作 T(n)=O(f(n)), 称 O(f(n)) 为算法的渐进时间复杂度, 简称时间复杂度
举个栗子:
- int sum = 0;
- int b = 100;
- for(int i = 0; i<= b;i++){
- sum += i;
- }
- // T(n) = n+1 = 100+1
- sum = (1+b)*b/2 // 同样也可以计算出结果, 但是 T(n) = 1
简而言之, 在 T(n)=O(f(n)) 中, 当 n 趋近无穷大时, 有 T(n)/f(n) = c, 极限值 c 是一个不为 0 的常数, 就叫 f(n) 是 T(n) 的同量级函数, 若求得 f(n) = n , 则 O(f(n)) =O(n).
各时间复杂度增长曲线:
各算法时间复杂度:
来源: https://www.cnblogs.com/coding-996/p/12267857.html