【C语言数据结构(基础篇)】第一站:时间复杂度与空间复杂度

简介: 【C语言数据结构(基础篇)】第一站:时间复杂度与空间复杂度

一、什么是时间复杂度和空间复杂度

1.算法效率

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

2.时间复杂度的概念

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

3.空间复杂度的概念

空间复杂度是对一个算法在运行过程中临时占用存储空间大小的量度 。空间复杂度不是程序占用 了多少bytes的空间,因为这个也没太大意义,所以空间复杂度算的是变量的个数。空间复杂度计 算规则基本跟实践复杂度类似,也使用大O渐进表示法。

二、如何计算常见的时间复杂度

1.大O的渐进表示法

我们看这样一段代码,并分析他的时间复杂度

void Func1(int N)
{
  int count = 0;
  for (int i = 0; i < N; ++i)
  {
    for (int j = 0; j < N; ++j)
    {
      ++count;
    }
  }
  for (int k = 0; k < 2 * N; ++k)
  {
    ++count;
  }
  int M = 10;
  while (M--)
  {
    ++count;
  }
  printf("%d\n", count);
}

我们可以计算出他的准确的次数,他的准确次数就是n平方+2n+10,但是呢,我们一般说时间复杂度的时候不会这么精确,因为随着n的增大,这个表达式的结果中n平方项的影响最大

例如

N = 10         F(N) = 130

N = 100       F(N) = 10210

N = 1000     F(N) = 1002010

......

因此,时间复杂度是一个估算,是去看表达式中影响最大的一项 ,本题的时间复杂度为o(

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

推导大O阶方法:

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

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

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

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

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

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

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

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

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

最好情况:1次找到

最坏情况:N次找到

平均情况:N/2次找到

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

2.一些时间复杂度的例子

(1)例1

void Func2(int N)
{
  int count = 0;
  for (int k = 0; k < 2 * N; ++k)
  {
    ++count;
  }
  int M = 10;
  while (M--)
  {
    ++count;
  }
  printf("%d\n", count);
}

他的准确次数为2n+10,时间复杂度为o(n)

(2)例2

// 计算Func3的时间复杂度?
void Func3(int N, int M)
{
  int count = 0;
  for (int k = 0; k < M; ++k)
  {
    ++count;
  }
  for (int k = 0; k < N; ++k)
  {
    ++count;
  }
  printf("%d\n", count);
}

他的时间复杂度为o(M+N),但是如果题目说了M远大于N,那么时间复杂度为O(M)

(3)例3

// 计算Func4的时间复杂度?
void Func4(int N)
{
  int count = 0;
  for (int k = 0; k < 100; ++k)
  {
    ++count;
  }
  printf("%d\n", count);
}

他的时间复杂度为O(1),因为他的时间是固定,不会随着n的增大而改变。他是一个常数,他的时间不变

(4)例4

// 计算strchr的时间复杂度?
const char* strchr(const char* str, char character)
{
    while (*str != '\0')
    {
        if (*str == character)
            return str;
        ++str;
    }
    return NULL;
}

对于这段代码,我们发现,他的功能是查找一个字符,那么他就有能出现一次就好,这是最好的情况,也可能查找了n次才找到,这是最坏情况,他的平均情况为n/2,但是我们实际中只看最坏情况,所以他的时间复杂度为o(n)

(5)例5

// 计算BubbleSort的时间复杂度?
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次比较,第二次是n-1,直到最后一趟是1

等差数列求和为后结果为(n+1)*n/2,所以他的时间复杂度为o(

这里也说明一点,不是说一层循环就是n,两层循环就是o(

(6)例6

// 计算BinarySearch的时间复杂度?
int BinarySearch(int* a, int n, int x)
{
  assert(a);
  int begin = 0;
  int end = n;
  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

那么最坏情况呢?

我们想假设是一个n个元素的数组,他每一次都需要除以2,最终结果为1。

因此我们可以逆向思考,1*2*2....*2=n,这就是我们二分查找的过程,所以,因此解得,所以查找次数就是,但是因为很多地方不方便写底数,所以算法的复杂度常常简写为,也就是但是我们会发现网上很多书或资料会写成,这种写法严格上来说是不对的,因为数学中这个是以10为底的,我们这个是以2为底的可以写成这样的。

(7)例7

// 计算阶乘递归Factorial的时间复杂度?
long long Factorial(size_t N)
{
  return N < 2 ? N : Factorial(N - 1) * N;
}

这是一个求阶乘的递归算法。其实他的运算次数我们可以看出是n,因为他递归了n次,每次递归运算的是,所以最终的时间复杂度就是

那么我们假如在里面又套了一层for循环

for(i=0;i<n;i++)
{
}

那么他的时间复杂度就是

3.总结

以上就是我们常见的时间复杂度计算

常见的时间复杂度有  

下图是各个时间复杂度的比较

我们从这个中也能看出来,O(1)与O(logN)几乎是一样的,也就是说他们几乎处于同一个量级,他们两个就是最优的

三、常见空间复杂度的计算

我们在前面已经介绍过空间复杂度的概念了

空间复杂度是对一个算法在运行过程中临时占用存储空间大小的量度 。空间复杂度不是程序占用 了多少bytes的空间,因为这个也没太大意义,所以空间复杂度算的是变量的个数。空间复杂度计 算规则基本跟实践复杂度类似,也使用大O渐进表示法。

也就是说,他只是计算变量的个数的。

1.例1

// 计算BubbleSort的空间复杂度?
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;
  }
}

对于我们这个代码而言,他其实总共就只创建了三个变量,end,exchange,i,所以空间复杂度就是O(1)

在这里大家疑惑就是,不是有一个循环吗,这样应该创建了很多次空间啊,这里要说的就是时间是累计的,但是空间是不累计的,空间我们使用完以后,就会将他还回去,所以每一次都是那三个变量。因此就是三个。

而且函数的形参是一般不记作空间复杂度的计算的,但也可以计入,因为就算计入,他的量级也是最小的,不会影响原本的空间复杂度。

2.例2

// 计算Fibonacci的空间复杂度?
long long* Fibonacci(size_t n)
{
    if (n == 0)
        return NULL;
    long long* fibArray = (long long*)malloc((n + 1) * sizeof(long long));
    fibArray[0] = 0;
    fibArray[1] = 1;
    for (int i = 2; i <= n; ++i)
    {
        fibArray[i] = fibArray[i - 1] + fibArray[i - 2];
    }
    return fibArray;
}

对于这个代码,这是一个斐波那契数列的代码,他采用的是循环的方式来求解,我们可以看出,如果计入形参的话,他的变量个数为n+5=6个,所以空间复杂度为O(N)

3.例3

// 计算阶乘递归Factorial的空间复杂度?
long long Factorial(size_t N)
{
  return N < 2 ? N : Factorial(N - 1) * N;
}

这是一个求阶乘的代码

我们知道,递归调用了N层,每次调用建立一个栈帧,每个栈帧使用了常数个空间O(1)

所以总的空间最大的消耗,空间复杂度就为O(N)

这里要注意,函数调用时候建立栈帧,返回时销毁栈帧。我们计算的是空间同时使用的最大消耗,而不能认为他最好是要销毁的,就认为他的空间复杂度是O(1),这与时间复杂度是类似的,计算的是最坏的情况。

四、有复杂度要求的算法题练习

1.消失的数字

题目链接:

面试题 17.04. 消失的数字 - 力扣(Leetcode)


 

题目描述:

(1)思路一

我们首先最先想到的办法当然就是先排序,然后一个一个找的,但是实际上这样是行不通的,我们在这里先给出一条结论,最快的排序也需要O(N*logN)的时间复杂度,显然不符合题目要求,所以排除此思路

(2)思路二

既然排序行不通,那么我们这样想,如果我们将1--N之间的数都加一块,然后将数组里面的数都加一块,然后一相减,是不是也可以啊,确实如此,这样一来时间复杂度也满足了我们的要求。这种思路较为简单,此处先不做代码展示了

(3)思路三

我们在操作符中学习过异或操作符,他的作用是,相同的二进制位进行异或,结果为0,0跟任何数异或,结果仍为该数,并且异或是满足交换律的

由此我们得到一种新的办法,让这个数组中的所有元素全部异或,放入一个数中,然后在让这个数与1~N之间的所有数进行异或,最终的结果就是不见的数字了,由此题目得到解决,我们给出代码

int missingNumber(int* nums, int numsSize){
    int i=0;
    int x=0;
    for(i=0;i<numsSize;i++)
    {
        x^=nums[i];
    }
    int j=0;
    for(j=0;j<numsSize+1;j++)
    {
        x^=j;
    }
    return x;
}

运行结果为

2.轮转数组

题目链接:189. 轮转数组 - 力扣(Leetcode)

题目描述:

(1)思路一

这道题我们简单分析一下,我们发现,右旋一次其实就是将最后一个元素放到最前面那个元素,然后剩下的都依次往后挪动即可,因此我们可以按照这个思路先写一下代码

void rotate(int* nums, int numsSize, int k){
    while(k--)
    {
        int tmp=nums[numsSize-1];
        int right=numsSize-2;
        for(right=numsSize-2;right>=0;right--)
        {
            nums[right+1]=nums[right];
        }
        nums[0]=tmp;
    }
}

当我们运行的时候,我们很遗憾的发现,超出时间了,我们发现这个测试用例给的很大。

因此我们这个思路是行不通的,我们要另寻他法

我们这个代码的时间复杂度是O(N*K)

(2)思路二

我们可以以空间换时间,也就是说,我们在创建一个数组,后面的k项放到新数组的前面,然后将nums数组的前n-k项放到新数组后面,最后将新数组的值都拷贝到原来的数组中,这样做似乎也没有问题,而且时间复杂度降低了,变成了O(N),但是空间复杂度也变成看O(N),而且万一题目再给出那么大的测试用例,那么空间都不够用了怎么办?时间也超时了怎么办?。所以综合来看,这个方法似乎也不是很好。

(3)思路三

这个方法其实我们讲过一个字符串逆序问题,在这个问题中我们提到过,这里给出链接:C语言经典题目之字符串逆序_青色_忘川的博客-CSDN博客        

这里我们最后一个题目是,逆序一句话,但不逆序单词。我们可以联想到,我们这个题逆序前n-k个数组元素,然后逆序后面k个元素,最后逆序整个数组,注意次序不可颠倒,否则会出错的,问题也就迎刃而解,这道题就相当于前面那片文章中题目的弱化版

但是我们会发现其实会出现这种报错,像这种错误都是内存泄漏之类的,

他最终给的一个用例是一个元素的时候,我们会发现,我们中间出现了numsSize-k这种的语句,这明显导致数组越界了。因此会报错。所以我们进行修改

void reverse(int* nums,int left,int right)
{
    while(left<right)
    {
        int tmp=nums[left];
        nums[left]=nums[right];
        nums[right]=tmp;
        left++;
        right--;
    }
}
void rotate(int* nums, int numsSize, int k){
    if(k>=numsSize)
    {
        k=k%numsSize;
    }
    reverse(nums,numsSize-k,numsSize-1);
    reverse(nums,0,numsSize-k-1);
    reverse(nums,0,numsSize-1);
}

运行结果为


总结

本站主要讲解了时间复杂度与空间复杂度的概念,以及一些经典的题目,包括两个力扣题,如果对你有帮助,不要忘记点赞加收藏哦!!!

关注我,后面的文章将更加精彩

相关文章
|
12天前
|
算法 数据处理 C语言
C语言中的位运算技巧,涵盖基本概念、应用场景、实用技巧及示例代码,并讨论了位运算的性能优势及其与其他数据结构和算法的结合
本文深入解析了C语言中的位运算技巧,涵盖基本概念、应用场景、实用技巧及示例代码,并讨论了位运算的性能优势及其与其他数据结构和算法的结合,旨在帮助读者掌握这一高效的数据处理方法。
23 1
|
20天前
|
存储 算法 搜索推荐
【趣学C语言和数据结构100例】91-95
本文涵盖多个经典算法问题的C语言实现,包括堆排序、归并排序、从长整型变量中提取偶数位数、工人信息排序及无向图是否为树的判断。通过这些问题,读者可以深入了解排序算法、数据处理方法和图论基础知识,提升编程能力和算法理解。
38 4
|
20天前
|
存储 机器学习/深度学习 搜索推荐
【趣学C语言和数据结构100例】86-90
本文介绍并用C语言实现了五种经典排序算法:直接插入排序、折半插入排序、冒泡排序、快速排序和简单选择排序。每种算法都有其特点和适用场景,如直接插入排序适合小规模或基本有序的数据,快速排序则适用于大规模数据集,具有较高的效率。通过学习这些算法,读者可以加深对数据结构和算法设计的理解,提升解决实际问题的能力。
38 4
|
20天前
|
存储 算法 数据处理
【趣学C语言和数据结构100例】81-85
本文介绍了五个经典算法问题及其C语言实现,涵盖图论与树结构的基础知识。包括使用BFS求解单源最短路径、统计有向图中入度或出度为0的点数、统计无向无权图各顶点的度、折半查找及二叉排序树的查找。这些算法不仅理论意义重大,且在实际应用中极为广泛,有助于提升编程能力和数据结构理解。
35 4
|
20天前
|
算法 数据可视化 数据建模
【趣学C语言和数据结构100例】76-80
本文介绍了五种图论算法的C语言实现,涵盖二叉树的层次遍历及广度优先搜索(BFS)和深度优先搜索(DFS)的邻接表与邻接矩阵实现。层次遍历使用队列按层访问二叉树节点;BFS利用队列从源节点逐层遍历图节点,适用于最短路径等问题;DFS通过递归或栈深入图的分支,适合拓扑排序等场景。这些算法是数据结构和算法学习的基础,对提升编程能力和解决实际问题至关重要。
38 4
|
20天前
|
存储 算法 vr&ar
【趣学C语言和数据结构100例】71-75
本文介绍了五个C语言数据结构问题及其实现,涵盖链表与二叉树操作,包括按奇偶分解链表、交换二叉树左右子树、查找节点的双亲节点、计算二叉树深度及求最大关键值。通过递归和遍历等方法,解决了理论与实际应用中的常见问题,有助于提升编程能力和数据结构理解。
33 4
|
20天前
|
存储 算法 C语言
【趣学C语言和数据结构100例】66-70
本书《趣学C语言和数据结构100例》精选了5个典型的数据结构问题及C语言实现,涵盖链表与数组操作,如有序集合的集合运算、有序序列表的合并、数组中两顺序表位置互换、三递增序列公共元素查找及奇偶数重排。通过详细解析与代码示例,帮助读者深入理解数据结构与算法设计的核心思想,提升编程技能。
32 4
|
13天前
|
存储 缓存 算法
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式,强调了合理选择数据结构的重要性,并通过案例分析展示了其在实际项目中的应用,旨在帮助读者提升编程能力。
31 5
|
12天前
|
并行计算 算法 测试技术
C语言因高效灵活被广泛应用于软件开发。本文探讨了优化C语言程序性能的策略,涵盖算法优化、代码结构优化、内存管理优化、编译器优化、数据结构优化、并行计算优化及性能测试与分析七个方面
C语言因高效灵活被广泛应用于软件开发。本文探讨了优化C语言程序性能的策略,涵盖算法优化、代码结构优化、内存管理优化、编译器优化、数据结构优化、并行计算优化及性能测试与分析七个方面,旨在通过综合策略提升程序性能,满足实际需求。
36 1
|
20天前
|
存储 机器学习/深度学习 算法
【趣学C语言和数据结构100例】61-65
本文介绍了五个关于C语言和数据结构的经典问题及其实现方法,涵盖查找链表共同后缀、删除重复节点、重新排列链表元素、合并有序链表以及特定条件下的链表排序。每个问题通过具体的算法设计,不仅展示了链表操作的灵活性,还强调了效率优化的重要性。通过这些问题的探讨,读者可以深入理解链表的基本操作和高级应用,提升解决实际问题的能力。
39 4