# algorithm

**Repository Path**: lqs2002/algorithm

## Basic Information

- **Project Name**: algorithm
- **Description**: 算法学习，还有数据结构、、、、、、
- **Primary Language**: Unknown
- **License**: Not specified
- **Default Branch**: algorithm
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 0
- **Forks**: 0
- **Created**: 2022-05-26
- **Last Updated**: 2022-07-30

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

# 算法与数据结构学习笔记
> 算法是程序的灵魂

---
## 初识复杂度

---
> 复杂度分为时间复杂度和空间复杂度，他们的表示形式相同(大O)，区别仅仅在于意义不同
### 时间复杂度

---
> #### 时间复杂度
> 可以理解为这个算法或者程序运行耗时，是常数时间的操作。
#### 常见的时间复杂度量级
```text
常数阶O(1)

对数阶O(logN)

线性阶O(n)

线性对数阶O(nlogN)

平方阶O(n²)

立方阶O(n³)

指数阶O(2^n)
```
##### 常数阶O(1)
> 无论代码执行了多少行，只要是没有循环等复杂结构，那这个代码的时间复杂度就都是O(1)
```java
int i = 1;
int j = 2;
++i;
j++;
int m = i + j;
```
##### 对数阶O(logN)
> 循环的时候不是自增或自减而是乘法
```java
int i = 1;
while(i<n)
{
    i = i * 2;
}
```
##### 线性阶O(n)
> 循环的时候自增或者自减
```java
for(i=1; i<=n; ++i)
{
   j = i;
   j++;
}
```

##### 线性对数阶O(nlogN)
> 将时间复杂度为O(logn)的代码循环N遍
```java
for(m=1; m<n; m++)
{
    i = 1;
    while(i<n)
    {
        i = i * 2;
    }
}
```
##### 平方阶O(n²)
> 把 O(n) 的代码再嵌套循环
```java
for(x=1; i<=n; x++)
{
   for(i=1; i<=n; i++)
    {
       j = i;
       j++;
    }
}
```

##### 立方阶O(n³)
> 把 O(n) 的代码再嵌套循环,然后再嵌套一次

##### 指数阶O(2^n)
> 比如{a,b} 的子集有{空},{a},{b},{a,b} 共4个。如果求{a,b,c}那么子集有{空},{a},{b},{c},{a,b},{a,c},{b,c},{a,b,c}共8个


### 空间复杂度

---
> #### 空间复杂度
> 可以理解为这个算法或者程序在运行的时候会消耗的资源（所占的空间）
#### 常见的空间复杂度量级
```text
O(1)

O(n)
```

##### O(1)
> 如果算法执行所需要的临时空间不随着某个变量n的大小而变化，此算法空间复杂度为一个常量，可表示为 O(1)，即 S(n) = O(1)
```java
int i = 1;
int j = 2;
int k = 1 + 2;
```

##### O(n)
```java
int n = 100
int j = 0;
int[] m = new int[n];
for (int i = 1; i <= n; ++i) {
   j = i;
   j++;
}
```
> 上述代码中，只有创建int数组分配空间时与n的大小有关，而for循环内没有再分配新的空间，因此，对应的空间复杂度为S(n) = O(n)


## 算法和数据结构的关系
> 1、数据结构是一门研究组织数据方式的学科，比如数组

> 2、程序 = 数据结构 + 算法

> 3、数据结构是算法的基础，想学好算法，就需要学好数据结构

## 数据结构

### 数据结构的分类

#### 线性结构
> 1、数据元素之间存在一对一的线性关系，如数组

> 2、线性结构有两种存储结构，顺序存储结构（连续）和链式存储结构（不一定连续）

> 3、线性结构常见的有：数组，队列，链表，栈


#### 非线性结构
> 非线性结构包括：二维数组，多维数组，广义表，树，图。非一对一的关系


### 稀疏数组和队列
#### 稀疏数组 
> 参考`com.lqs.datastructure.sparsearrayAndQueue.SparseArray`
*      稀疏数组就是将一个很大的二维数组，压缩成一个小的二维数组
*      数组的大小为 sparseArray[n+1][3],n表示有n个有效数据，除了默认的，比如零以外的都是有效数据
*      第一行存放的是原始数组的长度和宽度还有有效数据的个数（n个）
*      后面存放的是对应的n个有效数据的坐标和具体数据
*      可以将系数数组存放在文件中
*      应用场景：比如下棋的时候，恢复某一个棋局等

#### 队列（先进先出，有序列表）
> 队列可以用数组或者链表来模拟
#### 数组模拟
> 参考`com.lqs.datastructure.sparsearrayAndQueue.ArrayQueue`
#### 数组模拟环形队列
> 参考`com.lqs.datastructure.sparsearrayAndQueue.CircleArrayQueue`

### 链表
#### 单链表
> 参考`com.lqs.datastructure.linkedlist.SingleLinkedListDemo`