本文主要是介绍算法图解（1），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
配套代码：
https://github.com/egonSchiele/grokking_algorithms?tab=readme-ov-file
https://github.com/egonSchiele/grokking_algorithms?tab=readme-ov-file
理论
数据结构：组织和存储数据的方式，影响程序的性能和存储效率
算法：任何具有明确的步骤或规则的代码片段，用于旨在高效、准确地解决特定问题或执行某项任务。
设计模式：帮助开发者结构化和组织代码，提高代码的可维护性、可扩展性和复用性。
二分查找（查找算法）
原理：通过逐步将搜索范围缩小一半，快速定位目标元素的位置。
优点：高效，简单
缺点：通常仅适用于有序数组
时间：O(log n):因为每次查找都是上一次的一半，正好符合2的倍数
空间：
实例：给定排序好的数组，查找值为item的元素，在数组的什么索引位置
template <typename T>
int binary_search(const std::vector<T>& list, const int& item) {int low = 0;int high = list.size() - 1;while (low <= high) {int mid = (low + high) / 2;T guess = list[mid];if (guess == item) {return mid;}if (guess > item) {high = mid - 1;} else {low = mid + 1;}}return -1;
}对数
幂：一个数被多次相同的数相乘的结果：底数a^指数b，a 自身乘以自身 b 次
对数：幂运算的逆运算：给定一个幂的结果，求底数需要多少次方才能得到这个结果
转换：logb(x) = y -> b^y = x
以 e 为底的对数，记作 ln, 以 10 为底的对数，记作 log
时间复杂度
大O表示法：最坏情况运行时间： O(操作次数)：指出了随着元素数量的增加，算法运行时间（并非以秒为单位，而是随着输入规模（通常用 n表示）趋向于无穷大时，算法运行时间的增长趋势）
- O（1）常数时间，算法的运行时间不依赖于输入规模
- O(log n)对数时间，二分查找等分治算法
- O(n)线性时间，归并排序、快速排序
- O(n * log n)线性对数时间，速度较快，简单的线性查找或遍历
- O(n^2)平方时间，速度较慢，冒泡排序、选择排序。
- O(n^3)立方时间：通常是三重嵌套循环
- O(2^n)指数时间,暴力解法、某些递归算法
- O(n！)速度非常慢,暴力解法（旅行商问题）
空间复杂度
描述了算法在输入规模增加时，所需的存储空间的增长情况。考虑程序运行时占用内存的大小，而不是可执行文件的大小。
- O(1)常数空间，只使用有限个变量，不额外申请空间
- O(n)线性空间，需要额外数组或链表来存储输入数据。
- O(n2)平方空间，需要一个二维数组来存储数据。
复杂表达式化简
- 去掉运行时间中的加法常数项
- 去掉常数系数
- 只保留保留最高项，去掉数量级小一级的n
递归与斐波那契数
递归 是指在定义或解决问题时，函数直接或间接地调用自己。递归可以简化代码层面的复杂度，而非时间空间复杂度
递归时间复杂度：递归的次数 * 每次递归中的操作次数。
阶乘：一个正整数的所有小于或等于该数的正整数的乘积
int function2(int x, int n) {if (n == 0) {return 1; }return function2(x, n - 1) * x;
}斐波那契数:其中每一项是前两项之和，F(0)=0,F(1)=1
int fibonacci(int i) {if(i <= 0) return 0;if(i == 1) return 1;return fibonacci(i-1) + fibonacci(i-2);
}内存
- 栈区(Stack) ：由编译器自动分配释放，存放函数的参数值，局部变量的值等，其操作方式类似于数据结构中的栈。
- 堆区(Heap) ：一般由程序员分配释放，若程序员不释放，程序结束时可能由OS收回
- 未初始化数据区(Uninitialized Data)： 存放未初始化的全局变量和静态变量
- 初始化数据区(Initialized Data)：存放已经初始化的全局变量和静态变量
- 程序代码区(Text)：存放函数体的二进制代码
如何计算内存？根据数据类型占用的字节数
内存对齐：
经过内存对齐后，CPU访问内存的速度大大提升，因为CPU读取内存不是一个一个字节读取的，具体取多少个字节取决于硬件。如果对齐后一次寻址就可以找到数据，提高性能，但同样也会浪费内存资源，
这篇关于算法图解（1）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
