【数据结构】时间复杂度

一、什么是时间复杂度？

在计算机科学中，算法是具有时间复杂度的，并且算法的时间复杂度是一个函数，他定量的描述了该算法的运行时间。一个算法的运行时间，理论上我们是没法直接算出来的，只有程序在计算机运行起来，我们才能知道。但是我们需要每个算法的上机测试一遍吗？那多麻烦啊！所以才诞生了时间复杂度这个分析的函数方式。我们无法算出算法的运行时间，但我们肯定知道算法运行起来所花费的时间与算法语句的执行次数成正比，所以算法基本操作的执行次数，就是算法的时间复杂度。

二、如何计算时间复杂度？

实际中我们计算时间复杂度，我们不一定要算出算法精确的执行次数，我们只需要大概的执行次数，所以时间复杂度是一个估算，我们使用O的渐进表示法：O是用于描述函数渐进行为的数学符号。

推导时间复杂度的方法：
1.用常数1取代运行时间中的所有加法常数；
2.在修改后的运行次数函数中，只保留最高阶项；
3.如果最高阶项存在且不是1，则去除与这个项目相乘的常数；
4.如果两个for循环，且判断条件为两个未知数，则要按情况而定：
考虑远大于，远小于，或差不多大的情况
5.有些算法的时间复杂度存在最好，平均和最坏的情况：
例如：在一个长度为N的数组中搜索一个数据X
最好的情况：1次找到
最坏的情况：N次找到
平均的情况：N/2次找到
在实际运算中一般关注的是算法的最坏运行情况，所以数组中的时间复杂度为O(N)。
注意：在计算算法时间复杂度的时候，不能说一层循环就是o(N),两层嵌套循环就是O(N^2)

三，常见例题

请计算以下例题的时间复杂度。
1.

void Func1(int N)
{
	int count = 0;
	int i = 0;
	int j = 0;
	int k = 0;
	//N^2
	for (i = 0; i < N; i++)
	{
		for (j = 0; j < N; j++)
		{
			count++;
		}
	}
	//2N
	for (k = 0; k < 2 * N; k++)
	{
		count++;
	}
	int M = 10;
	//10
	while (M--)
	{
		count++;
	}
	printf("%d\n", count);
	return 0;
}
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

T(n)=N的平方+2N+10,时间复杂度为O(N^2)。

void Func2(int N)
{
	int count = 0;
	int k = 0;
	//2N
	for (k = 0; k < 2 * N; k++)
	{
		count++;
	}
	int M = 10;
	//10
	while (M--)
	{
		count++;
	}
	printf("%d\n", count);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

T(N)=2*N+10,时间复杂度为O(N)。

void Func3(int N, int M)
{
	int count = 0;
	int k;
	for (k = 0; k < M; k++)
	{
		count++;
	}
	for (k = 0; k < N; k++)
	{
		count++;
	}
	printf("%d\n", count);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

3.这个算法有两个未知数
时间复杂度：
若没有给条件，O(M+N)
若M远大于N，则O(M)
若M远小于N，则O(N)

void Func(int N)
{
	int count = 0;
	int k = 0;
	//100是常数哦
	for (int k = 0; k < 100; k++)
	{
		count++;
	}
	printf("%d\n", count);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12

常数次，时间复杂度为O(1)

const char* strchar(const char* str, char ch)
{
	while (*str != '\0')
	{
		if (*str == ch)
		{
			return str;
		}
		str++;//向后遍历
	}
	return NULL;//找不到就返回空指针
}
1
2
3
4
5
6
7
8
9
10
11
12

假设字符串的长度为N，“abcdefg”
最好的情况：‘a’,O(1)
最坏的情况：‘x’,O(N)
平均的情况：‘d’,O(N/2)
看最坏的情况，所以这个算法的时间复杂度为O(N)

6.冒泡排序法的时间复杂度

#include<stdio.h>
void bubble_sort(char* a, int sz)
{
	int i = 0;
	int j = 0;
	int temp = 0;
	int flag = 0;
	for (i = 0; i < sz - 1; i++)
	{
		flag = 1;
		for (j = 0; j < sz - 1 - i; j++)
		{
			if (a[j] > a[j + 1])
			{
				temp = a[j];
				a[j] = a[j + 1];
				a[j + 1] = temp;
				flag = 0;
			}
		}
		if (flag == 1)
		{
			break;
		}
	}
}
int main()
{
	char arr[] = { 10,9,8,7,6,5,4,3,2,1 };
	int sz = sizeof(arr) / sizeof(arr[0]);
	bubble_sort(arr, sz);
	int i;
	for (i = 0; i < sz; i++)
	{
		printf("%d ", arr[i]);
	}
	return 0;
}

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
38
39

冒泡排序法的时间复杂度
第一趟比较(N-1)次，第二趟比较(N-2)次，第三趟比较(N-3)次
T(n)=(N-1)+(N-2)+(N-3)+…+3+2+1=(N-1)(1+N-1)/2
时间复杂度为O(N^2)

7.折半（二分）查找算法的时间复杂度

#include<stdio.h>
int main()
{
	int arr[] = { 1,2,3,4,5,6,7,8,9,10 };
	int k = 7;
	int sz = sizeof(arr) / sizeof(arr[0]);
	int left = 11;
	int right = sz - 1;
	while (left <= right)
	{
		int mid = (left + right) / 2;
		if (arr[mid] < k)
		{
			left = mid + 1;
		}
		else if (arr[mid] > k)
		{
			right = mid - 1;
		}
		else
		{
			printf("找到了，下标为%d\n", mid);
			break;
		}
	}
	if (left > right)
	{
		printf("找不到\n");
	}
	return 0;
}


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

折半查找算法的时间复杂度，我们知道折半算法，找一次，范围就缩小一半
不如我们从找到的剩下一个元素为起点，往前推：
1x2x2x2x2…x2=N个元素
2^X=N,X=logN；
所以折半查找算法的时间复杂度为：O(logN)(往往把底数2省略不写)

void Func(int n)
{
	int i;
	//i=0,初始化语句只执行1次
	//i<n,判断指向n+1次
	//i++，调整语句执行n次
	for (i = 0; i < n; i++)
	{
		printf("123\n");//执行n次
	}
	return 0;//执行1次
}
1
2
3
4
5
6
7
8
9
10
11
12

T(n)=3n+3,时间复杂度为O(N).

void Func(int n)
{
	int i = 0;
	int j = 0;
	//n^2
	for (i = 0; i < n; i++)
	{
		for (j = 0; j < n; j++)
		{
			printf("123\n");
		}
	}
	//n
	for (i = 0; i < n; i++)
	{
		printf("1\n");
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

T(n)=n的平方+n,时间复杂度为O(N^2)

void Func(int n)
{
	int i;
	int j;
	for (i = 0; i < n; i++)//n
	{
		//i=0,n
		//i=1,n-1
		//i=2,n-2
		//...
		//n+(n-1)+(n-2)+(n-3)+...3+2+1=n(1+n)/2
		for (j = i; j < n; j++)
		{
			printf("123\n");
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

时间复杂度为O(N^2)

void Func(int n)
{
	int i;
	for (i = 1; i < n; i*=2)
	{
		printf("123\n");
	}
}
1
2
3
4
5
6
7
8

时间复杂度为O(logN)

12.阶乘递归的时间复杂度

long long Factorial(int N)
{
	//三目操作符
	return N < 2 ? N : Factorial(N - 1)*N;
}
1
2
3
4
5

F(10)
F(9)*10
F(8)*9
…
F(2)*3
F(1)*2
return 1
递归调用了N次，每次递归运算O(1),整体时间复杂度就是O(N)

#include<stdio.h>
int main()
{
	int n;
	int i;
	int j;
	for (i = 1; i < n; i++)//N
	{
		j = 1;
		while (j < n)
		{
			j = j * 2;//logN
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

线性对数阶其实很好理解，就是把O(logN)循环N边，那么它的时间复杂度就是O(NlogN)

14.O(m*n)

#include<stdio.h>
int main()
{
	int x, m, i, j;
	//m和n都是未知数
	for (x = 1; x <= m; x++)
	{
		for (i = 1; i <= n; i++)
		{
			j = i;
			j++;
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

15.O(n^3),O(n的k次方阶)
这也很好理解，参考O(n^2),O(n的三次方)就是三层n循环，O(n的k次方阶)就是k层n循环咯

四，时间复杂度的大小关系