代码随想录记录（一）
算法性能分析
时间复杂度 算法超时空间复杂度递归算法总结内存管理
不同语言例如：C++的内存管理计算程序占用内存内存对齐 TIPS
代码随想录记录（一） 算法性能分析 时间复杂度- 大O表示上界，作为算法的最坏情况运行时间上界，在算法中O为一般情况，并不是严格的上界。不同的数据规模，其算法的时间复杂度也不同由于不同算法的时间复杂度在不同数据输入规模下有差异，因此在考虑用哪种算法也要视数据规模来定。O(1)常数阶 < O(log n)对数阶 < O(n)线性阶 < O(n^2)平方阶 < O(n^3)立方阶
在利用了三种递归后，发现并不是所有的递归算法的时间复杂度都是O(log n)
空间复杂度对一个算法在运行过程中占用内存空间大小的量度，记作S(n)=O(f(n)
递归算法的空间复杂度 = 每次递归的空间复杂度 * 递归深度
- 程序运行时内存大小与程序本身的大小不同
空间复杂度就是考虑运行时占用内存的大小，且不是准确算出（因为程序内存的开销会受到多种因素的影响）只是预先大体评估。
O(1)——程序运行开辟的内存空间不随n的变化而变化，即为一个常量。O(n)——当消耗空间和输入参数n保持线性增长。O(logn)——即在递归时出现。
版本一：
int fibonacci(int i){
if(i<=0) return 0;
if(i=1) return 1;
return fibonacci(i-1)+fibonacci(i-2)
}
时间复杂度：
即递归的次数*每次递归的时间复杂度
我们可以用二叉树来理解：
每次输入的i为根节点，分支分别为i-1，i-2，由于一棵深度（按根节点深度为1）为k的二叉树最多可以有 2^k - 1 个节点。
所以该递归算法的时间复杂度为O(2^n)，这个复杂度是非常大的，随着n的增大，耗时是指数上升的。
时间复杂度：O(2^n)
空间复杂度：O(n)
版本二
int fibonacci(int first, int second, int n) {
if (n <= 0) {
return 0;
}
if (n < 3) {
return 1;
}
else if (n == 3) {
return first + second;
}
else {
return fibonacci(second, first + second, n - 1);
}
}
此时就不用两次递归了。
因为每次递归的时候n减1，即只是递归了n次，所以时间复杂度是 O(n)。
同理递归的深度依然是n，每次递归所需的空间也是常数，所以空间复杂度依然是O(n)。
时间复杂度：O(n)
空间复杂度：O(n)
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-RcaFjxAI-1646462008653)(C:UserslenovoAppDataRoamingTyporatypora-user-imagesimage-20220302210929483.png)]
内存管理 不同语言| 语言 | 内存管理 |
|---|---|
| C/C++ | 申请和释放完全靠自己管理 |
| Java | JVM内存管理 |
| Python | 私有堆空间管理，所有的python对象和数据结构都存储在私有堆空间中。程序员没有访问堆的权限，只有解释器才能操作。 |
注：python的基本数据类型所用的内存会要远大于存放纯数据类型所占的内存
例如：C++的内存管理- 分为固定部分和可变部分固定部分：代码区存储二进制代码；数据区存储全局变量、静态变量、常量等。可变部分：栈区（Stack）由编译器自动分配释放，存放函数的参数值，局部变量的值等，其操作方式类似于数据结构中的栈。 堆区（Heap）：一般由程序员分配释放，若程序员不释放，程序结束时可能由OS收回，是动态开辟的空间，存放new出来的对象在堆区中的真实数据。需要手动回收。而Java、Python的话则不需要程序员去考虑内存泄漏的问题，虚拟机都做了这些事情
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-jjxIyE4H-1646462008654)(C:UserslenovoDesktop日常技能文案计算机占用内存.png)]
指针的大小不同的原因：
安装64位的操作系统的计算机内存都已经超过了4G，也就是指针大小如果还是4个字节的话，就已经不能寻址全部的内存地址，所以64位编译器使用8个字节的指针才能寻找所有的内存地址。
内存对齐- 为什么会有内存对齐：
平台原因：
某些硬件平台只能在某些地址处取某些特定类型的数据，否则抛出硬件异常,为了同一个程序可以在多平台运行，需要内存对齐
硬件原因：内存对齐后，CPU访问内存速度显著提升。 TIPS
在历经6小时的艰苦奋斗（脑残编辑中……终于
我的Vscode又可以运行C++了，Vscode历经；1四次的删改，再加上MinGW的折磨。。。。我的leetcode正式开始
硬件原因：内存对齐后，CPU访问内存速度显著提升。
