# zlsy-leetcode-learning

**Repository Path**: zhouliangde/zlsy-leetcode-learning

## Basic Information

- **Project Name**: zlsy-leetcode-learning
- **Description**: 力扣学习
- **Primary Language**: Java
- **License**: Not specified
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 0
- **Forks**: 0
- **Created**: 2020-03-12
- **Last Updated**: 2020-12-19

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

[toc]
# 一、时间复杂度和空间复杂度



## 1、含义

- 时间复杂度：就是说执行算法需要消耗的时间长短，越快越好。比如你在电脑上打开计算器，如果一个普通的运算要消耗1分钟时间，那谁还会用它呢，还不如自己口算呢。
- 空间复杂度：就是说执行当前算法需要消耗的存储空间大小，也是越少越好。本来计算机的存储资源就是有限的，如果你的算法总是需要耗费很大的存储空间，这样也会给机器带来很大的负担。


## 2、时间复杂度的计算

### 2.1、表示方法
- 我们一般用“大O符号表示法”来表示时间复杂度：T(n) = O(f(n))，n是影响复杂度变化的因子，f(n)是复杂度具体的算法。

### 2.2、常见的时间复杂度量级
- 常数阶O(1)
- 线性阶O(n)
- 对数阶O(logN)
- 线性对数阶O(nlogN)
- 平方阶O(n²)
- 立方阶O(n³)
- K次方阶O(n^k)
- 指数阶(2^n)


#### 2.2.1、常数阶O(1)
```java
int a = 1;
int b = 2;
int c = 3;
```
假如上面的代码没执行一行就需要1个时间单位，那么上面就需要三个时间单位，那是不是这段代码的时间复杂度就是O（n）呐？

不是的，因为大O不是代表算法的执行时间的，而是用来表示代码执行时间的增加趋势的。

上面的代码并没有随着某个变量的增长而增长，无论这个代码有多长，都可以用O（1）来表示它的复杂度。

#### 2.2.2、线性阶O（n）
```java
   /**
     * 时间复杂度：线性阶
     *
     * @param n
     */
    private static int linearOrder(int n) {
        int j = 0;
        int l = 0;
        for (int i = 0; i < n; i++) {
            l++;
            j++;
        }
        return j;
    }
```

上面的代码，会随着n的大小，l++和j++都会执行n次，时间复杂度为O(n)

#### 2.2.3、对数阶O(logN)
```java
int i = 1;
while(i < n) {
    i = i * 2;
}

```
可以看到每次循环的时候 i 都会乘2，那么总共循环的次数就是log2n，因此这个代码的时间复杂度为O(logn)。
这儿有个问题，为什么明明应该是O(log2n）,却要写成O(logn)呢？
其实这里的底数对于研究程序运行效率不重要，写代码时要考虑的是数据规模n对程序运行效率的影响，常数部分则忽略，同样的，如果不同时间复杂度的倍数关系为常数，那也可以近似认为两者为同一量级的时间复杂度。


#### 2.2.4、线性对数阶O(nlogN)
```java
for(m = 1; m < n; m++) {
    i = 1;
    while(i < n) {
        i = i * 2;
    }
}
```
线性对数阶O(nlogN) 其实非常容易理解，将时间复杂度为O(logn)的代码循环N遍的话，那么它的时间复杂度就是 n * O(logN)，也就是了O(nlogN)。

#### 2.2.5、平方阶O(n²)
```java
for(x=1; i <= n; x++){
   for(i = 1; i <= n; i++) {
       j = i;
       j++;
    }
}
```
把 O(n) 的代码再嵌套循环一遍，它的时间复杂度就是 O(n²) 了。


#### 2.2.6、立方阶O(n³)
```java
for(k=1,k<=n;k++){
    for(x=1; i <= n; x++){
       for(i = 1; i <= n; i++) {
           j = i;
           j++;
        }
    }
}
```

#### 2.2.6、K次方阶O(n^k)
就是嵌套K次


## 3、空间复杂度

### 3.1、空间复杂度 O(1)
如果算法执行所需要的临时空间不随着某个变量n的大小而变化，即此算法空间复杂度为一个常量，可表示为 O(1)。

```java
int i = 1;
int j = 2;
++i;
j++;
int m = i + j;
```
代码中的 i、j、m 所分配的空间都不随着处理数据量变化，因此它的空间复杂度 S(n) = O(1)。

### 3.1、空间复杂度 O(n)

```java
int[] m = new int[n]
for(i=1; i <= n; ++i) {
   j = i;
   j++;
}
```

这段代码中，第一行new了一个数组出来，这个数据占用的大小为n，后面虽然有循环，但没有再分配新的空间，因此，这段代码的空间复杂度主要看第一行即可，即 S(n) = O(n)。