时间复杂度的分析看一下你就懂了_论文的时间复杂度分析

提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档

---

复杂度分析

什么是复杂度分析?
代码执行的效率以及占用的物力资源
作用: 评价一段代码/一段算法优劣的一种重要指标

复杂度分析的过程: 一般情况下,排除硬件的影响复杂度分析一般分为两种:

1. 时间复杂度
2. 空间复杂度

1.1时间复杂度

什么是时间复杂度

• 作用: 考量代码执行效率的一个非常重要的指标
• 全称: 渐进时间复杂度
• 抛开算法运行的软硬件环境,只考虑算法与问题规模之间的关系
• 算法的时间复杂度反映了程序执行时间随输入规模增长而增长的量级,在很大程度上能很好地反映出算法的优劣
• 算法执行时间需要通过依据该算法编制的程序在计算机上运行时所消耗的时间来度量

一般使用O表示时间复杂度,O(1) O(n) O(n^2) O(n^3) O(log2n)

public static int sum(int[]nums){						
	int sum = 0;										
	for( int num : nums) sum+=num;
	return sum;
}
O(n)
n是nums中元素的个数算法和n呈线性关系

为什么要用大O,叫做O(n)?
时间复杂度一般采用大O表示,评估算法的一种方式
O(1)：不是代表只有一行代码，只是说没有遍历去影响他，他的时间复杂度是常量级的

public void sum1(){
sout("和="+sum);
}
public void sum1(){
sout("和="+sum);
 sout("和="+sum);
 sout("和="+sum);
 sout("和="+sum);
}

public void sum1(){
sout("和="+sum);
 sout("和="+sum);
 //.....100行代码
 sout("和="+sum);
 sout("和="+sum);
}

O(n):单层for循环，算法的时间复杂度只跟n的大小有关
O(n^2):嵌套for循环
public void sum1(int[] array){
for(int i=0;i<array.length;i++){
for(int j=0;j<array.length;j++){
sum = array[i] * array[j];
} } }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

举个例子:
T = 2 * n + 2 复杂度是O(n)
T = 2000n + 10000 时间复杂度是O(n)
T = 2 * n * n + 2 时间复杂度是O(n^2)
T = 2 * n + 200n+10 时间复杂度是O(n^2)
问题: O(n^2)的执行一定会比O(n) 消耗的更多么?
不一定
当n=1时 T=2000 * n+10000时间复杂度时O(12000)
T=1 * n * n+10时间复杂度是O(11)
但是当n=10000的时候 T = 2000 * n +10000 时间复杂度是O(2001 0000)
T = 1.* n * n +0 时间复杂度是1 0000 0000
结论: 当n趋于无穷大的时候,O(n^2)的时间复杂度一定高于O(n)