当前位置:   article > 正文

算法的时间复杂度(详解)_解释 算法的时间复杂度

解释 算法的时间复杂度

前言:

算法(Algorithm):就是定义良好的计算过程,他取一个或一组的值为输入,并产生出一个或一组值作为 输出。简单来说算法就是一系列的计算步骤,用来将输入数据转化成输出结果

一、算法效率

1.1 如何衡量一个算法的好坏

如何衡量一个算法的好坏呢?比如对于以下斐波那契数列

  1. long long Fib(int N)
  2. {
  3. if(N < 3)
  4. return 1;
  5. return Fib(N-1) + Fib(N-2);
  6. }

斐波那契数列的递归实现方式非常简洁,但简洁一定好吗?那该如何衡量其好与坏呢?

1.2 算法的复杂度

算法在编写成可执行程序后,运行时需要耗费时间资源和空间(内存)资源 。因此衡量一个算法的好坏,一般 是从时间和空间两个维度来衡量的,即时间复杂度和空间复杂度。

时间复杂度主要衡量一个算法的运行快慢,而空间复杂度主要衡量一个算法运行所需要的额外空间。在计算机发展的早期,计算机的存储容量很小。所以对空间复杂度很是在乎。但是经过计算机行业的迅速发展,计算机的存储容量已经达到了很高的程度。所以我们如今已经不需要再特别关注一个算法的空间复杂度。

复杂度在校招中的考察

常见复杂度对比

 

二、时间复杂度

2.1 时间复杂度的概念

时间复杂度的定义:在计算机科学中,算法的时间复杂度是一个函数,它定量描述了该算法的运行时间。一 个算法执行所耗费的时间,从理论上说,是不能算出来的,只有你把你的程序放在机器上跑起来,才能知道。但是我们需要每个算法都上机测试吗?是可以都上机测试,但是这很麻烦,所以才有了时间复杂度这个 分析方式。一个算法所花费的时间与其中语句的执行次数成正比例,算法中的基本操作的执行次数,为算法的时间复杂度。

即:找到某条基本语句与问题规模N之间的数学表达式,就是算出了该算法的时间复杂度。

  1. // 请计算一下Func1++count语句总共执行了多少次?
  2. void Func1(int N)
  3. {
  4. int count = 0;
  5. for (int i = 0; i < N; ++i)
  6. {
  7. for (int j = 0; j < N; ++j)
  8. {
  9. ++count;
  10. }
  11. }
  12. for (int k = 0; k < 2 * N; ++k)
  13. {
  14. ++count;
  15. }
  16. int M = 10;
  17. while (M--)
  18. {
  19. ++count;
  20. }
  21. printf("%d\n", count);
  22. }

实际中我们计算时间复杂度时,我们其实并不一定要计算精确的执行次数,而只需要大概执行次数,那么这里我们使用大O的渐进表示法。

2.2 大O的渐进表示法

大O符号(Big O notation):是用于描述函数渐进行为的数学符号。

推导大O阶方法:

1、用常数1取代运行时间中的所有加法常数。

2、在修改后的运行次数函数中,只保留最高阶项。

3、如果最高阶项存在且不是1,则去除与这个项目相乘的常数。得到的结果就是大O阶。

使用大O的渐进表示法以后,Func1的时间复杂度为:

O(N^2)

N = 10 F(N) = 100

N = 100 F(N) = 10000

N = 1000 F(N) = 1000000

通过上面我们会发现大O的渐进表示法去掉了那些对结果影响不大的项,简洁明了的表示出了执行次数。

另外有些算法的时间复杂度存在最好、平均和最坏情况:

最坏情况:任意输入规模的最大运行次数(上界)

平均情况:任意输入规模的期望运行次数

最好情况:任意输入规模的最小运行次数(下界)

例如:在一个长度为N数组中搜索一个数据x

最好情况:1次找到

最坏情况:N次找到

平均情况:N/2次找到

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

三、常见时间复杂度计算举例

实例1:

  1. // 计算Func2的时间复杂度?
  2. void Func2(int N)
  3. {
  4. int count = 0;
  5. for (int k = 0; k < 2 * N; ++k)
  6. {
  7. ++count;
  8. }
  9. int M = 10;
  10. while (M--)
  11. {
  12. ++count;
  13. }
  14. printf("%d\n", count);
  15. }

基本操作执行了2N+10次,通过推导大O阶方法知道,时间复杂度为 O(N)

实例2:

  1. // 计算Func3的时间复杂度?
  2. void Func3(int N, int M)
  3. {
  4. int count = 0;
  5. for (int k = 0; k < M; ++k)
  6. {
  7. ++count;
  8. }
  9. for (int k = 0; k < N; ++k)
  10. {
  11. ++count;
  12. }
  13. printf("%d\n", count);
  14. }

基本操作执行了M+N次,有两个未知数M和N,时间复杂度为 O(N+M)

实例3:

  1. // 计算Func4的时间复杂度?
  2. void Func4(int N)
  3. {
  4. int count = 0;
  5. for (int k = 0; k < 100; ++k)
  6. {
  7. ++count;
  8. }
  9. printf("%d\n", count);
  10. }

基本操作执行了100次,通过推导大O阶方法,时间复杂度为 O(1)

注:O(1)代表常数次

实例4:

  1. // 计算strchr的时间复杂度?
  2. const char * strchr ( const char * str, int character );

我们分析一下

  1. while (*str)
  2. {
  3. if (*str == charcter)
  4. return str;
  5. else
  6. ++str;
  7. }

基本操作执行最好1次,最坏N次,时间复杂度一般看最坏,时间复杂度为 O(N)

实例5: 

  1. // 计算BubbleSort的时间复杂度?
  2. void BubbleSort(int* a, int n)
  3. {
  4. assert(a);
  5. for (size_t end = n; end > 0; --end)
  6. {
  7. int exchange = 0;
  8. for (size_t i = 1; i < end; ++i)
  9. {
  10. if (a[i - 1] > a[i])
  11. {
  12. Swap(&a[i - 1], &a[i]);
  13. exchange = 1;
  14. }
  15. }
  16. if (exchange == 0)
  17. break;
  18. }
  19. }

基本操作执行最好N次,最坏执行了N*(N-1)/2次,通过推导大O阶方法+时间复杂度一般看最坏,时间复杂度为 O(N^2)

实例6:

  1. // 计算BinarySearch的时间复杂度?
  2. int BinarySearch(int* a, int n, int x)
  3. {
  4. assert(a);
  5. int begin = 0;
  6. int end = n - 1;
  7. // [begin, end]:begin和end是左闭右闭区间,因此有=
  8. while (begin <= end)
  9. {
  10. int mid = begin + ((end - begin) >> 1);
  11. if (a[mid] < x)
  12. begin = mid + 1;
  13. else if (a[mid] > x)
  14. end = mid - 1;
  15. else
  16. return mid;
  17. }
  18. return -1;
  19. }

分析二分查找的时间复杂度: 

查找区间的变化:

N
N/2 
N/4
N/8
…… 

1

二分查找什么情况下最坏?查找区间只剩一个数,或者找不到,也就是:N/2/2…/2 = 1

查找了多少次,就是除了多少个2,假设查找了x次 2^x = N

那么查找次数为:x=logN(底数忽略不写)

则时间复杂度: O(logN)

因为写的时候需要支持专业公式,否则不好写底数,时间复杂度当中,为了方便,logN可以省略底数直接写成logN,其他底层不能省略(其他底数也很少出现)

实例7:

  1. // 计算阶乘递归Fac的时间复杂度?
  2. long long Fac(size_t N)
  3. {
  4. if(0 == N)
  5. return 1;
  6. return Fac(N-1)*N;
  7. }

递归时间复杂度:所有递归调用次数累加(等差数列) 

通过计算分析发现基本操作递归了N次,时间复杂度为O(N)。

实例8:

  1. // 计算斐波那契递归Fib的时间复杂度?
  2. long long Fib(size_t N)
  3. {
  4. if(N < 3)
  5. return 1;
  6. return Fib(N-1) + Fib(N-2);
  7. }

如下图所示:每次递归都是以2倍的形式增长,累加求和,我们可以使用等比数列错位相减法

  

计算分析发现基本操作递归了2^N次,时间复杂度为O(2^N)。

这种算法基本上是废了,只有理论意义,实践中太慢了。 

四、复杂度的OJ练习

1.消失的数字

OJ链接:消失的数字

 

思路一:先排序,再依次查找,如果下一个值不等于前一个+1,下一个值就是消失数字,如果我们使用冒泡排序进行排序,就不符合题目要求了,因为它的时间复杂度是O(N^2)

思路二:求和0到N,再依次减去数组中的值,剩下的那个值就是消失数字,累加的时间复杂度为O(N),如果N的数字比较大可能会导致栈溢出。

代码如下:

思路三:我们可以使用异或,把数组中0到N的元素全部异或起来,相同为0相异为1,最后那个数字就是消失的数字,这样还可以防止栈溢出

代码如下:

  1. int missingNumber(int* nums, int numsSize)
  2. {
  3. int x = 0;
  4. int N = numsSize;
  5. for(int i = 0;i<numsSize;i++)
  6. {
  7. x^=nums[i];
  8. }
  9. for(int j = 0;j<=numsSize;j++)
  10. {
  11. x^=j;
  12. }
  13. return x;
  14. }

2.轮转数组

 OJ链接:轮转数组

思路一:先写出旋转一次的函数,在调用k次,k的真实旋转次数为k%=numsSize

代码如下:

但是超出时间限制了

我们分析一下:

最坏情况 :k%N等于N-1 -> O(N^2)

最好情况:k%N等于0

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

思路二:我们使用三段逆置,我们先让前n-k个逆置一下,然后再把后k个逆置一下,最后整体逆置。

代码如下:

  1. void reverse(int*a,int left,int raght)
  2. {
  3. while(left < raght)
  4. {
  5. int temp = a[left];
  6. a[left] = a[raght];
  7. a[raght] = temp;
  8. ++left;
  9. --raght;
  10. }
  11. }
  12. void rotate(int* nums, int numsSize, int k)
  13. {
  14. k %= numsSize;
  15. reverse(nums,0,numsSize-k-1);
  16. reverse(nums,numsSize-k,numsSize-1);
  17. reverse(nums,0,numsSize-1);
  18. }

时间复杂度为O(N),我们也可以使用memcpy


总结

时间复杂度是衡量算法执行效率的重要指标,它表示算法随输入数据规模增长时执行时间的变化趋势。优化时间复杂度可以节省计算资源、提高系统性能、满足实时性要求,并提升用户体验。在设计算法时,应充分考虑时间复杂度的优化,以实现高效、稳定的性能表现。 

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/你好赵伟/article/detail/703425
推荐阅读
相关标签
  

闽ICP备14008679号