时间复杂度的计算_时间复杂度计算

1.时间复杂度

时间复杂度的定义：在计算机科学中，算法的时间复杂度是一个函数，它定量描述了该算法的运行时间。
一个算法所花费的时间与其中语句的执行次数成正比例。所以算法中的基本操作的执行次数，为算法的时间复杂度。

大O用来表示程序执行次数的

大O的渐进法表示

1、用常数1取代运行时间中的所有加法常数。
2、在修改后的运行次数函数中，只保留最高阶项。
3、如果最高阶项存在且不是1，则去除与这个项目相乘的常数。得到的结果就是大O阶。

void Func1(int N)
 {
 int count = 0;//执行次数为1
 for (int i = 0; i < N ; ++ i) 
 {
  for (int j = 0; j < N ; ++ j)
   {
   ++count;//1.count执行次数为N^2
   }
 }
 for (int k = 0; k < 2 * N ; ++ k) 
 {
   ++count;//2.count执行次数为2*N
 }
  int M = 10;
while (M--)
 {
 ++count;//count执行次数为10次
 }
printf("%d\n", count);//执行次数为1
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

所以此函数执行次数的关系式为：

N总=1+n^2+2n+10+1=2n+12+n*n;

当n趋于无穷大时n^2是2*n和12的高阶无穷小，所以N总的大小不用考虑这两项，此外高阶无穷小前的系数在n->无穷的时候不考虑。

保留最高阶项，忽略最高阶前的系数

所以此函数的时间复杂度为O(n^2)

常见的时间复杂度有：常数阶O(1),对数阶O(log2n),线性阶O(n), 线性对数阶O(nlog2n),平方阶O(n2)，立方阶O(n3) k次方阶,指数阶O(2^n)。

注意O(1)表示常数次，这个常数次可以很大

如果算法的执行时间不随着问题规模n的增加而增长，即使算法中有上千条语句，其执行时间也不过是一个较大的常数。此类算法的时间复杂度是O(1)。
eg:

int main()
{
	int i = 0;
	for (i = 0; i < 1000000000; i++)
	{
		;
	}
	return 0;
}
1
2
3
4
5
6
7
8
9

循环次数虽然多，但这只是很大的常数，所以时间复杂度仍为O（1）

最好、平均和最坏情况

例如：查找算法

最好情况：查找一次就找到了。

最坏情况：查找了N次查找到了。

平均情况：（1+N）/2

在实际中一般情况关注的是算法的最坏运行情况，所以数组中搜索数据时间复杂度为O(N)

具体函数分析

一：

void Func2(int N) {
int count = 0;//执行1次
for (int k = 0; k < 2 * N ; ++ k) {
 ++count; }//执行2*N
int M = 10;//执行1次
while (M--) {
 ++count; }//执行10次
printf("%d\n", count);//执行一次
}
1
2
3
4
5
6
7
8
9

所以执行次数函数为

N总=2*n+12;

大O法只保留最高阶，且忽略最高阶前的系数
所以Func2（）的时间复杂度为O(N)

二：

void Func3(int N, int M) {
int count = 0;//执行1次
for (int k = 0; k < M; ++ k) {
 ++count; }//执行M次
for (int k = 0; k < N ; ++ k) {
 ++count; }//执行N次
printf("%d\n", count);//执行1次
}
1
2
3
4
5
6
7
8

所以执行次数的函数为：
N总=m+n+2;
注意：在这里不能确定m,n，有两个未知数会影响执行次数，且这两个未知数的阶数相同，所以不能轻易省略。

所以大O表示Func3（）函数的时间复杂度为O(M+N)

三：

void Func4(int N) {
int count = 0;//执行1次
for (int k = 0; k < 100; ++ k) {
 ++count; }//执行100次
printf("%d\n", count);
}
1
2
3
4
5
6

所以执行次数的函数为：
N总=11
算法的执行时间不随着问题规模n的增加而增长

所以大O表示Func4（）函数的时间复杂度为O（1）

四：

char* strchr(char *s, char c)
{
    while(*s != '\0' && *s != c)
    {
        ++s;//执行N次，与传入函数的字符串有关
    }
    return *s==c ? s : NULL;
}
1
2
3
4
5
6
7
8

所以函数strchar（）执行次数的表达式为:
最好为1次，最坏为N次
大O法表示为其最坏的情况.

所以strchr函数的时间复杂度为O（N）

五：

//冒泡排序法
void BubbleSort(int* a, int n) {
assert(a);
for (size_t end = n; end > 0; --end) {
 int exchange = 0;
 for (size_t i = 1; i < end; ++i)
 {
 if (a[i-1] > a[i])
 {
 Swap(&a[i-1], &a[i]);
 exchange = 1;
 }
 }
 if (exchange == 0)
 break;}}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

在面对复杂的函数问题时我们要想清楚函数执行方式

以上代码的含义是：

先给函数传入一个长度为n的数组首元素地址，以及数组长度

exchange的作用为记录数组是否交换，

1.如果exchange的值在经历了第一次循环后还是0，表明该数组已经有序，不需要交换，直接返回。只是经过了一次查找数组

所以可以知道算法最好情况用大O法表示为O(N)；

2.在经历了第一次循环N-1次后end减少，下一次循环次数变为N-2次。
所以所以函数BubbleSort（）执行次数的表达式为:

(N-1)+(N-2)+(N-3)…+1=(1+N-1)*(N-1)/2=N(N-1)/2

大O法表示为其最坏的情况.

大O法只保留最高阶，且忽略最高阶前的系数O(N^2)

六：

int BinarySearch(int* a, int n, int x) {//二分查找法找数字
assert(a);
int begin = 0;
int end = n-1;
while (begin < end) {
 int mid = begin + ((end-begin)>>1);//找中间位置
 if (a[mid] < x)
 begin = mid+1;
 else if (a[mid] > x)
 end = mid;
 else
 return mid; }
return -1; }
1
2
3
4
5
6
7
8
9
10
11
12
13

由上图我们可以知道查找一次，N被分成2份。查找二次,N被分成4份，
设查找的f(x)次,此时N被分成2^f(x)份。
2^f(x)=N,解得f(x)=logN，这个就是它的执行次数。

所以用大O法表示为O(logN)

七：

long long Factorial(size_t N) {
return N < 2 ? N : Factorial(N-1)*N; }
//这个代码是递归求阶乘
1
2
3

递归的时间复杂度=递归次数*每次递归过程中函数的执行次数

阶乘递归的次数是从N到1，共有N次。每一次递归过程中函数执行次数是1次（一句三目操作符）

所以Factorial()的时间复杂度为O(N*1)=O(N);

注意：
如果还是递归N次，但每一次递归都有一个
for(int i=0;i<N;i++){}；这时每次递归过程中函数执行次数为N次
时间复杂度变为O(N*N)=O(N^2)

八：

long long Fibonacci(size_t N) {
return N < 2 ? N : Fibonacci(N-1)+Fibonacci(N-2);斐波那契数列
}
1
2
3

为了方便举例子，这里先从N=4的时候说起

每一次函数的执行次数为1

所以大O表示O(2^N*1)