用处：**时间复杂度 ** 定性地 描述算法的运行速度。

定性 定量

请问下面代码执行次数是多少？

int fun1(void) {
	printf("小云真帅！");
	return 0;
}

int fun2(int n) {
	for (int i = 0; i < n; i++) {
		printf("小云真丑！");
	}
	return 0;
}

int fun1(void) {
	printf("小云真帅！");//1次
    printf("小云真帅！");//1次
    printf("小云真帅！");//1次
    printf("小云真帅！");//1次
    printf("小云真帅！");//1次
    .......//1000
	return 0;//1次
}
//1000次
//T(n) = 1000

int fun2(int n) {
	for (int i = 0; i < n; i++) {// 1  n+1 n
		printf("小云真丑！"); // n
	}
	return 0;// 1
}
//T(n) = 3n+3

一道代码的执行次数可以用T(n)来表示，n读作问题规模，可以简单理解为输入数据的大小

代码的时间量度

那么很显然执行的次数越多，那么它执行的速度就会越慢，所以用T(n)就可以用来描述算法的运行时间。

但是作为衡量代码速度的一个依据，但代码量一旦比较多，比较复杂的时候，它就没有那么好用了，我们还需要一条一条去数，而且函数调用函数或者是递归的情况的话，那就更加麻烦，所以一般我们会用T(n)简化的一种估算值，来衡量代码的速度。

渐进时间复杂度

简化就是只保留重要信息来反映代码的速度，在算法设计中，常常不进行精确分析，而是取最坏的情况，来衡量这个算法的速度，用O(f(n))表示。

时间复杂度是与问题规模的关系

• 推导时间复杂度的原则：
  • 1.如果运行时间是常数量级，用常数1表示。
  • 2.只保留时间函数中的最高阶项。
  • 3.如果最高阶项存在，则省去最高阶项前面的系数。

比如：

$$\begin{align*} &T(n) = 2 = O(1) \newline &T(n) = 3n+3 = O(n) \newline \newline \newline \newline\newline\newline\newline\newline\newline\newline\newline &T(n) = 5n^3+6666n^2+233 = \end{align*} $$

int fun1(void) {
	printf("小云真帅！");
	printf("小云真帅！");
	printf("小云真帅！");
	printf("小云真帅！");
	printf("小云真帅！");
	return 0;
}


int fun2(int n) {
	for (int i = 0; i < n; i++) {
		printf("小云真丑！");
	}
	return 0;
}

int fun3(int n) {
	for(int i = 0;i < n;i++)
    {
		for (int j = 0; j < n; j++) 
        {
            for(int a = 0; a < n ;a++)
				printf("芝麻好吃！");
		}
	}
	return 0;
}

int fun4(int n) {
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			printf("芝麻好吃！");
		}
	}
	for (int j = 0; j < n; j++) {
		printf("花生难吃！");
	}
	return 0;
}

int fun5(int n) {
	if(n>100){
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				printf("芝麻好吃！");
			}
		}
	}
	else{
		for (int j = 0; j < n; j++) {
			printf("花生难吃！");
		}
	}
	return 0;
}

辨析一下奇怪的时间复杂度

1:

int fun6(int n) {
	for (int i = 0; i < n; i++)
    {
		for (int j = i; j < n; j++)
        {
			printf("多吃蔬菜。");
		}
	}
	return 0;
}

先看看T(n)

$$T(n) = n+(n-1)+(n-2)+(n-3)+.......2+1=O(n^2)$$

2:

int fun7(int n) {
	for(int i = 1; i<n ;i*=2)
    {
		printf("多喝热水。");
	}
	return 0;
}

int fun8(int n) {
	for(int i = 1; i<n ;i+=2)
    {
		printf("就不喝热水。");
	}
	return 0;
}

名称	复杂度
常数时间	O(1)
对数时间	O(log n)
线性时间	O(n)
线性对数时间	O(n log n)
二次时间	O(n^2)
三次时间	O(n^3)
指数时间	O(2^n)

空间复杂度

int fun8(int n) 
{
	int a = n - 1;
	if(a == 1){
		return 1;
	}
	fun8(a);
}

S(n) = n个 = O(n)

int f1(int n) {
    if(n = 0) return 0;
    return f1(n-1);
}

int f2(int n) {
    if(n = 0) return 0;
    return f1(n/2);
}


int fibonacci(int i) {
       if(i <= 0) return 0;
       if(i == 1) return 1;
       return fibonacci(i-1)+ fibonacci(i-2);
}