• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

时间复杂度的计算

互联网 diligentman 2个月前 (03-31) 13次浏览

文章目录

    • 1.时间复杂度
    • 大O的渐进法表示
    • 最好、平均和最坏情况
    • 具体函数分析

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("%dn", count);//执行次数为1
}

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

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;
}

循环次数虽然多,但这只是很大的常数,所以时间复杂度仍为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("%dn", count);//执行一次
}

所以执行次数函数为

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("%dn", count);//执行1次
}

所以执行次数的函数为:
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("%dn", count);
}

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

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

四:

char* strchr(char *s, char c)
{
    while(*s != '' && *s != c)
    {
        ++s;//执行N次,与传入函数的字符串有关
    }
    return *s==c ? s : NULL;
}

所以函数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;}}

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

以上代码的含义是:

先给函数传入一个长度为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; }

时间复杂度的计算

时间复杂度的计算

时间复杂度的计算
由上图我们可以知道查找一次,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; }
//这个代码是递归求阶乘

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

阶乘递归的次数是从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);斐波那契数列
}

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

时间复杂度的计算
时间复杂度的计算
每一次函数的执行次数为1

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


程序员灯塔
转载请注明原文链接:时间复杂度的计算
喜欢 (0)