数据结构与算法——时间与空间复杂度
目录
时间复杂度
大O记法
执行次数=执行时间
大O记法有以下几个规则：
①用常数1取代运行时间中的所有加法常数;
如：O(5),用O(1)来表示。
②在修改后的运行次数中，只保留高阶项;
如：O(2n^2+3n+1),则时间复杂度为O(n^2)
③如果最高阶项存在，且常数因子不为1，则去除与这个项相乘的常数;
如：O(5n),则时间复杂度应该为O(n)
常见的时间复杂度：
| 描述 | 增长的数量级 | 说明 | 举例 |
| 常数级别 | 1 | 普通语句 | 将两个数相加 |
| 对数级别 | logN | 二分策略 | 二分查找 |
| 线性级别 | N | 循环 | 找出最大元素 |
| 线型对数级别 | NlogN | 分治思想 | 归并排序 |
| 平方级别 | N^2 | 双层循环 | 检查所有元素对 |
| 立方级别 | N^3 | 三层循环 | 检查所有三元组 |
| 指数级别 | 2^N | 穷举查找 | 检查所有子集 |
复杂程度从低到高依次为：
O(1)<O(logn)<O(n)<O(nlogn)<O(n^2)<O(n^3)<O(2^n)
空间复杂度
通常选择空间换时间,一般说复杂度是指时间复杂度
java中有以下常见的内存占用情况
①java中基本数据类型内存占用情况:
| 数据类型 | 内存占用字节数 |
|---|---|
| byte | 1 |
| short | 2 |
| int | 4 |
| long | 8 |
| float | 4 |
| double | 8 |
| boolean | 1 |
| char | 2 |
②计算机访问内存都是一次一个字节
③一个引用（机器地址）需要8个字节表示
如：例如: Date date = new Date(),则date这个变量需要占用8个字节来表示
④创建一个对象，比如new Date()，除了Date对象内部存储的数据(例如年月日等信息)占用的内存，该对象本身也有内存开销，每个对象的自身开销是16个字节，用来保存对象的头信息。
⑤一般内存的使用，如果不够8个字节，都会被自动填充为8字节
本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
THE END
二维码