#### 符号及其表示
$O$符号表示、表示问题的规模。
- 常规的：$O(1)$、$O(logn)$、$O(\sqrt{n})$
1. $O(1)$
$O(1)$只是常量级时间复杂度的一种表示方法，并不是指只执行了$1$行代码。比如以下代码,即便有$3$行，它的时间复杂度也是$O(1)$。
```
 int i = 8;
 int j = 6;
 int sum = i + j;
```
因此：只要代码的执行时间不随$n$的增大而增大，这样代码的时间复杂度都记作$O(1)$，即便有成千上万行。
```
for(int i = 0;i<100000;i++){
	  i++；
}
```
即便是循环，但是代码的执行时间不随$n$的增大而增大，所以这段代码的时间复杂度依然是$O(1)$

2. $O(logn)、O(nlogn)$

```
 i=1; // 1
 while (i <= n)  { // 2
   i = i * 2; // 3
 }
```
代码1的时间复杂度是$O(1)$,而代码$2$和代码$3$是循环代码，所以根据简单的时间复杂度分析办法，我们只关注循环执行次数最多的一段代码即可，因此这里我们关注代码$2$和$3$即可。我们先看下代码$3$：
```
i = i * 2; // 3
```
变量$i$从$1$开始取，每次循环都$×2$，当大于$n$时，循环结束。所以$i$的取值：

>$2^0、2^1、2^2、2^3......2^x = n$

所以我们只需要知道$x$的值，就知道代码$3$执行次数了。而为何最后“$=n$"呢，是因为$i$的最大可能值就是$n$。因此$x$的值就是$x = log_2n$,所以这段代码的时间复杂度就是$O(log_2n)$
```
 i=1; // 1
 while (i <= n)  { //2
   i = i * 3; // 3
 }
```
从以上分析不难得出，这段代码的时间复杂度是$O(log_3n)$.而采用大$O$复杂度表示法的时候，可以忽略系数，因为不管是乘以$3$也好，还是乘以$2$也好，对变化趋势有影响的始终是 $n$，所以代码$3$的时间复杂度用大$O$复杂度表示法表示为"对数阶$O(logn)$"，而根据时间复杂度分析方法之乘法法则：嵌套代码复杂度是嵌套内外代码复杂度的乘积，所以代码$2$和$3$这段代码的时间复杂度用大$O$复杂度表示法表示为"线性对数阶$O(nlogn)$"。而代码$1$的时间复杂度为$O(1)$，根据时间复杂度分析法之加法法则：总复杂度等于量级最大的那段代码的复杂度，所以以上两段代码的复杂度是"线性对数阶$O(nlogn)$"。

3. $O(m+n)、O(m * n)$
```
int cal(int m, int n) {
		int sum_1 = 0;
		int i = 1;
		for (; i < m; ++i) {
	    	sum_1 = sum_1 + i;
		}
	
		int sum_2 = 0;
		int j = 1;
		for (; j < n; ++j) {
	    	sum_2 = sum_2 + j;
		}
	
		return sum_1 + sum_2;
	}
```
由于数据规模有两个，分别是$m$和$n$，而此时我们并不知道$m$和$n$谁的量级大，所以"复杂度分析法之加法法则（总复杂度等于量级最大的那段代码的复杂度）"失效，这段代码的时间复杂度是$O(m+n)$.但是乘法法则依然有效：
```
int cal(int m, int n) {
	int sum_1 = 0;
	int i = 1;
	int sum_2 = 0;
	int j = 1;
	for (; i < m; ++i) {
		sum_1 = sum_1 + i;
		for (; j < n; ++j) {
			sum_2 = sum_2 + j;
		}
	}
	return sum_1 + sum_2;
}
```
通过上面的分析，不难得出，这段代码的时间复杂度是 $O(m * n)$。

这里要注意：$O(logn) < O(\sqrt{n})$,举例：$n = 10^6$,$log(10^6) = 20$，而$\sqrt{10^6} = 1000$
- 多项式的：$O(n)$、$O(n^2)$、$O(n^3)$、...
- 介于$O(n)$、$O(n^2)$，还有$O(n \cdot log_n)$、$O(n \cdot \sqrt{n})$
- 大规模的：$O(2^n) < O(n!)$
这里要注意：$O(2^n) < O(n!)$,举例：$10! = 3628800$,$2^{10} = 1024$

$O(1) < O(logn) < O(\sqrt{n}) < O(n) < O(n \cdot logn) < O(n \cdot \sqrt{n}) < O(n^2) < O(n^3) < O(2^n) < O(n!)  $

#### 具体代码分析举例：
```
	//O(n)
	for (int i=1; i<=n; i++){
		
	}
	
	//O(n^2)
	for (int i=1; i<=n; i++){
		for (int j=1; j<=n; j++){
			
		}
	}
	
	//O(n^2)  n*(n-1)/2 n^3+n^2+n+1
	for (int i=1; i<=n; i++){
		for (int j=i+1; j<=n; j++){
			
		}
	}
	
	//n/2 + n/3 + n/4 ... +n/n = O(nlog(n))
	for(int i=2; i<=n; i++){
		for(int j=i*2 ; j<=n; j+=i){
			
		}
	}
	
	//O(sqrt(n))  
	for(int i=2; i*i<=n; i++){
		if(n%i == 0){
			ret ++ ;
			if (n/i != i) ret++;
		}
	}
	
	
	//O(sqrt(n))
	for(int i=2; i*i<=n; i++){
		if(n%i == 0){
			//while循环里语句每运行一次，n就会变小
			//而且这个i是大于等于2的
			//这就意味着这里while循环最多会执行log(n)次 
			while(n%i == 0){
				n/=i;
			}
		}
	}
	
	//2^n 枚举所有的组合、子集 
	
	//n! 枚举全排列（递归+回溯）
	
```

符号及其表示

$O$符号表示、表示问题的规模。 - 常规的：$O(1)$、$O(logn)$、$O(\sqrt{n})$ 1. $O(1)$ $O(1)$只是常量级时间复杂度的一种表示方法，并不是指只执行了$1$行代码。比如以下代码,即便有$3$行，它的时间复杂度也是$O(1)$。

 int i = 8;
 int j = 6;
 int sum = i + j;

因此：只要代码的执行时间不随$n$的增大而增大，这样代码的时间复杂度都记作$O(1)$，即便有成千上万行。

for(int i = 0;i<100000;i++){
      i++；
}

即便是循环，但是代码的执行时间不随$n$的增大而增大，所以这段代码的时间复杂度依然是$O(1)$

$O(logn)、O(nlogn)$

 i=1; // 1
 while (i <= n)  { // 2
   i = i * 2; // 3
 }

代码1的时间复杂度是$O(1)$,而代码$2$和代码$3$是循环代码，所以根据简单的时间复杂度分析办法，我们只关注循环执行次数最多的一段代码即可，因此这里我们关注代码$2$和$3$即可。我们先看下代码$3$：

i = i * 2; // 3

变量$i$从$1$开始取，每次循环都$×2$，当大于$n$时，循环结束。所以$i$的取值：

$2^0、2^1、2^2、2^3......2^x = n$

所以我们只需要知道$x$的值，就知道代码$3$执行次数了。而为何最后“$=n$"呢，是因为$i$的最大可能值就是$n$。因此$x$的值就是$x = log_2n$,所以这段代码的时间复杂度就是$O(log_2n)$

 i=1; // 1
 while (i <= n)  { //2
   i = i * 3; // 3
 }

从以上分析不难得出，这段代码的时间复杂度是$O(log_3n)$.而采用大$O$复杂度表示法的时候，可以忽略系数，因为不管是乘以$3$也好，还是乘以$2$也好，对变化趋势有影响的始终是 $n$，所以代码$3$的时间复杂度用大$O$复杂度表示法表示为"对数阶$O(logn)$"，而根据时间复杂度分析方法之乘法法则：嵌套代码复杂度是嵌套内外代码复杂度的乘积，所以代码$2$和$3$这段代码的时间复杂度用大$O$复杂度表示法表示为"线性对数阶$O(nlogn)$"。而代码$1$的时间复杂度为$O(1)$，根据时间复杂度分析法之加法法则：总复杂度等于量级最大的那段代码的复杂度，所以以上两段代码的复杂度是"线性对数阶$O(nlogn)$"。

$O(m+n)、O(m * n)$

int cal(int m, int n) {
        int sum_1 = 0;
        int i = 1;
        for (; i < m; ++i) {
            sum_1 = sum_1 + i;
        }

        int sum_2 = 0;
        int j = 1;
        for (; j < n; ++j) {
            sum_2 = sum_2 + j;
        }

        return sum_1 + sum_2;
    }

由于数据规模有两个，分别是$m$和$n$，而此时我们并不知道$m$和$n$谁的量级大，所以"复杂度分析法之加法法则（总复杂度等于量级最大的那段代码的复杂度）"失效，这段代码的时间复杂度是$O(m+n)$.但是乘法法则依然有效：

int cal(int m, int n) {
    int sum_1 = 0;
    int i = 1;
    int sum_2 = 0;
    int j = 1;
    for (; i < m; ++i) {
        sum_1 = sum_1 + i;
        for (; j < n; ++j) {
            sum_2 = sum_2 + j;
        }
    }
    return sum_1 + sum_2;
}

通过上面的分析，不难得出，这段代码的时间复杂度是 $O(m * n)$。

这里要注意：$O(logn) < O(\sqrt{n})$,举例：$n = 10^6$,$log(10^6) = 20$，而$\sqrt{10^6} = 1000$ - 多项式的：$O(n)$、$O(n^2)$、$O(n^3)$、... - 介于$O(n)$、$O(n^2)$，还有$O(n \cdot log_n)$、$O(n \cdot \sqrt{n})$ - 大规模的：$O(2^n) < O(n!)$ 这里要注意：$O(2^n) < O(n!)$,举例：$10! = 3628800$,$2^{10} = 1024$

$O(1) < O(logn) < O(\sqrt{n}) < O(n) < O(n \cdot logn) < O(n \cdot \sqrt{n}) < O(n^2) < O(n^3) < O(2^n) < O(n!) $

具体代码分析举例：

    //O(n)
    for (int i=1; i<=n; i++){

    }

    //O(n^2)
    for (int i=1; i<=n; i++){
        for (int j=1; j<=n; j++){

        }
    }

    //O(n^2)  n*(n-1)/2 n^3+n^2+n+1
    for (int i=1; i<=n; i++){
        for (int j=i+1; j<=n; j++){

        }
    }

    //n/2 + n/3 + n/4 ... +n/n = O(nlog(n))
    for(int i=2; i<=n; i++){
        for(int j=i*2 ; j<=n; j+=i){

        }
    }

    //O(sqrt(n))  
    for(int i=2; i*i<=n; i++){
        if(n%i == 0){
            ret ++ ;
            if (n/i != i) ret++;
        }
    }


    //O(sqrt(n))
    for(int i=2; i*i<=n; i++){
        if(n%i == 0){
            //while循环里语句每运行一次，n就会变小
            //而且这个i是大于等于2的
            //这就意味着这里while循环最多会执行log(n)次 
            while(n%i == 0){
                n/=i;
            }
        }
    }

    //2^n 枚举所有的组合、子集 

    //n! 枚举全排列（递归+回溯）

—— 本文来自火龙信奥（义乌睿码科技）：义乌青少年信息学奥赛与编程教育平台，专注 CSP-J/S、NOIP、GESP 竞赛培训，线上线下融合教学，助力编程升学。网址：hlcoding.com

第一课、时间复杂度

符号及其表示

具体代码分析举例：