算法的性能分析概括成时间复杂度和空间复杂度两部分;
1. 时间复杂度
通常指算法运行的时间(大O记法只保留最高次项,忽略低次项和常数项)
2. 空间复杂度
通常指算法在运行过程中占用内存空间大小,记做S(n)=O(f(n))。
O(1):随着n的变化,所需开辟的内存空间并不会随着n的变化而变化,即算法空间复杂度为一个常量;eg. for (int i = 0; i < n; i++) { ... }
O(n):消耗空间和输入参数n保持线性增长;eg. for (int i = 0; i < n; i++) { a[i] = i; }
3. 硬件性能(力扣上超时一般也是判断是否超过1s执行的次数,可以推算代码大概运行时间)
CPU配置:2.7 GHz Dual-Core Intel Core i5,1 GHz = 1000MHz = 10亿Hz,(1Hz即CPU的一次脉冲,也叫时钟周期)
计算执行代码所需的时间,例如 1+2=3(分成将1存入寄存器,将2存入寄存器,运算,保存运算结果)
运行过程中有时间损耗,所以可推算 O(n) 大约为 5 亿左右,O(n2) 大概为 O(n) 开根号,以此类推。
4. 递归算法
递归算法的时间复杂度 = 递归的次数 * 每次递归的时间复杂度。(ab = n 推出 b = logan)
递归算法的空间复杂度 = 每次递归的空间复杂度 * 递归深度(每次递归所需的空间都被压到调用栈里,每次递归结束就是本次数据弹栈的过程,所以栈最大的长度就是递归的深度)。
5. JVM
Java 依赖JVM来做内存管理,不了解JVM内存管理的机制,很可能会因一些错误的代码写法而导致内存泄漏或内存溢出。
6. 内存对齐
平台原因:不是所有的硬件平台都能访问任意内存地址上的任意数据,某些硬件平台只能在某些地址处取某些特定类型的数据,否则抛出硬件异常。为了同一个程序可以在多平台运行,需要内存对齐。
硬件原因:经过内存对齐后,CPU访问内存的速度大大提升。
注:CPU一次寻址四个字节,因此char在内存对齐的时候会产生3个空位。eg. struct node { int num; char cha;}st;st占用的内存是 4个字节(int) + 内存对齐产生的4个字节内存(char,3个内存为空)
标签:分析,递归,性能,CPU,算法,内存,对齐,复杂度 From: https://www.cnblogs.com/LinxhzZ/p/16705180.html