# study-algorithm

**Repository Path**: Andy_Chen7/study-algorithm

## Basic Information

- **Project Name**: study-algorithm
- **Description**: No description available
- **Primary Language**: Unknown
- **License**: Not specified
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 0
- **Forks**: 0
- **Created**: 2025-09-25
- **Last Updated**: 2025-10-27

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

## 算法
### 从是否存在确切值区分为硬计算类算法和软计算类算法。
1. 硬计算类算法：精确求解。
2. 软计算类算法：更注重逼近解决问题，而不是精确求解。

## 数据结构
### 从宏观上定义为连续结构和跳转结构。任何数据结构都一定由这两个结构拼凑出来的。

## 二分搜索
### 时间复杂度：O(log N)
### 启示：二分搜索不一定发生在有序数组上（例如寻找某一峰值问题）。哪怕数组是无序的，若能确定“某侧必有/某测必没有"，则能进行二分。

## 时间复杂度
#### 一个和数据量有关、只需要高阶项、不需要低阶项和常数项的操作次数表达式。
#### 关心：数据量与常量操作数量之间最高阶的关系，趋近于哪一最高级别。
1. 常数操作：O(1)，固定时间的操作，执行时间与数据量无关。 常见如：位运算 > 算数运算 > 寻址 > 哈希。 
2. 严格固定流程的算法，一定要强调最差情况。 例如对于插入排序，它的情况在O(N) ~ O(N^2)之间。因此它的时间复杂度是O(N^2)。
3. 在算法流程中利用随机行为作为重要的部分，需要考虑平均或者期望复杂度，只考虑最差情况是毫无意义的。
   1. 生成相邻值不同的数组
   2. 随机快速排序
4. 均摊，例如动态数组的扩容（等比数列），均摊下来时间复杂度为O(N)。并查集、单调队列、单调栈、哈希表等结构均有均摊概念。
5. 不要用代码结构判断时间复杂度，这是个常见并比较低级的错误。只能通过对算法流程的充分理解才能分析出来。
   1. 只用一个while循环实现冒泡排序，时间复杂度还是O(N^2)。
   2. N * (1 + 1/2 + 1/3 + 1/4 + ... + 1/N) 这个流程的时间复杂度为O(N * log N)
6. 常见复杂度一览：O(1) < O(log N) < O(N) < O(N * log N) < O(N^2) < O(N^k) < O(2^N) < O(k^N) < O(N!)
7. 可以直接判断某个方法能不能通过一个题目，根据数据量来猜解法。
## 空间复杂度
#### 又称做额外空间复杂度，支持某一功能的实现所额外开辟出来的空间（出参入参所占空间不计入）。

## 最优解
#### 先满足时间复杂度最优，再尽量少用空间解。


## 递归序的解释
### 用递归实现二叉树的三序遍历
```
    1      递归序：1，2，4，4，4，2，5，5，5，2，1，3，6，6，6，3，7，7，7，3，1
   / \     先序：1，2，4，5，3，6，7
  2   3    中序：4，2，5，1，6，3，7
 / \ / \   后序：4，5，2，6，7，3，1
4  5 6  7
```

## 递归
- 画调用图来分析递归是非常重要且有利的。
- 底层是利用系统栈来实现的。
- 任何递归函数都一定可以改成非递归来实现，不用系统帮忙压栈（虚拟机栈），自己压栈（堆内存）。
- 递归改成非递归的必要性
  - 工程上几乎一定要改，对于确定数据量再大，递归也一定不深，例如归并排序、快速排序、线段树、很多的平衡树等无所谓。
  - 算法笔试或者比赛中（能通过就不改）
  - 
## master公式
- 所有子问题规模相同的递归才能用master公式。T(n) = a * T(n/b) + O(n^c)，a、b、c为常数。
- 如果log(b, a) < c，则复杂度为O(n^c)
- 如果log(b, a) > c，则复杂度为O(n^log(b, a))
- 如果log(b, a) == c，则复杂度为O(n^c * log(n))
- T(n) = 2 * T(n/2) + O(n * log(n))，时间复杂度为O(n * (log(n) ^ 2))