小工具知识网

当前位置: 首页 > 行业知识 > 【Super数据结构】数据结构入门first step!了解些概念和时空复杂度计算!

行业知识

【Super数据结构】数据结构入门first step!了解些概念和时空复杂度计算!

2026-11-16 11:49:31 来源:互联网转载

��关于此专栏:Super数据结构专栏将使用C/C++语言介绍顺序表、链表、栈、队列等数据结构,每篇博文会使用尽可能多的代码片段+图片的方式。

博主首页:Jammingpro

归属专栏:Super数据结构

每日努力一点点,技术累计看得见

文章目录

  • 数据结构是什么
  • 什么是算法
  • 数据结构和算法的重要性
  • 复杂度计算
    • 时间复杂度计算
    • 空间复杂度计算
    • 常见复杂度对比

      数据结构是什么

      数据结构从表面意思看,就是存储数据的物理结构。在我们编写程序时,我们需要考虑以什么样的方式存储数据。这就类似于生活中,我们喝咖啡会用马克杯,喝排骨汤会用碗。虽然用马克杯喝排骨汤也是可以的,但用碗会更合适。因而,我们在编写代码时,需要寻找合适的数据结构来存储数据。

      上面是使用大白话解释的数据结构的概念,下面看一下正式的数据结构的概念:数据结构是计算机存储、组织数据的方式,指相互之间存在一种或多种特定关系的数据元素的集合。

      什么是算法

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

      在生活中,煮饭需要先洗米、再加水、再打开电饭煲开关。这里的输入就是大米,而输出就是可食用的白米饭,从输入得到输出的一系列步骤就是算法。

      数据结构和算法的重要性

      要吃饭得用碗,想存数据就得定下数据结构;要吃饭就得先做饭,想得到输出就得经过一系列算法步骤。在编程过程中,数据结构与算法无处不在,且非常重要。但数据结构、算法数量繁多,后续将在专栏中陆续介绍。

      这篇博文并不介绍某一数据结构,而是先来谈论怎么计算效率。我们在考虑选择哪一种算法时,无非考虑这个算法快不快、用的内存多不多。下面将介绍如何计算算法的时间效率和空间效率(即算法的时间复杂度和空间复杂度)。

      复杂度计算

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

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

      下面是一段使用循环计算1+2+3+…+100000的代码

      long long Count(){long long sum = 0;for(int i = 1; i return (100000 * (1 + 100000)) / 2;}int count = 0;for(int i = 0; i 大O符号(Big O notation):是用于描述函数渐进行为的数学符号。

      下面我们再聊聊推导大O阶方法:

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

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

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

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

      NF(N)
      10100
      10010000
      10001000000

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

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

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

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

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

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

      最好情况:1次找到

      最坏情况:N次找到

      平均情况:N/2次找到

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

      知道了大O表示法是什么、怎么算,那我们就可以着手练一下啦~

      第1个小可爱(Φ皿Φ)

      int Func(int N){int count = 0;for(int i = 0; i  

      揭晓答案的时刻:O(N)

      为什么呢?第一个for循环执行8*N次,第二个for循环执行666次, F ( N ) = 2 ∗ N + 666 F(N)=2*N+666 F(N)=2∗N+666。根据大O表示法规则,只保留最高次项,并将最高次项前的常数去除。因此,最终答案为O(N)。

      第2个小可爱(Φ皿Φ)

      void LaoBa(int M, int N){for(int i = 0; i  

      揭晓答案的时刻:O(M+N)

      为什么呢?第一个for循环执行M次,第二个for循环执行N次。M和N并没有任何关系,不存在谁更高次,谁更低次的问题。例如:M=100000,N=1,又例如:M=1,N=100000呢?因而M和N都应该保留,即O(M+N)。

      第3个小可爱(Φ皿Φ)

      void singSong(int N){for(int i = 0; i  

      揭晓答案的时刻:O(1)

      为什么呢?这里的for循环执行了100次,与传入的变量N无关。因为常数应被替换为1,因此答案为O(1)。

      第4个小可爱(Φ皿Φ)

      const char* strchr(const char* str, int character);

      揭晓答案的时刻:O(N)

      为什么呢?这个函数是C语言库自带的函数,它的作用是再str字符串中寻找第一个等于character的字符。因此,这个函数必须遍历整个str字符串,故答案为O(N)。

      第5个小可爱(Φ皿Φ)

      void BubbleSort(int arr[], int len){int exchange = 0;for(int i = 0; i  arr[j + 1]){Swap(&arr[j], &arr[j + 1]);exchange = 1;}}if(exchange == 0){break;}}}

      揭晓答案的时刻: O ( N 2 ) O(N^2) O(N2)

      为什么呢?冒泡排序需要内层和外层两层循环,外层需要执行N-1次,内层随外层i的增大而每次减小。第一次内层循环需要执行N-2次,第二次内层循环需要执行N-3次,…。内层循环的执行次数随i增大,每次减少1,形成等差数列。F(N)=(N-2)(N-2+1)/2。因此答案为O(N^2)。

      第6个小可爱(Φ皿Φ)

      int BinarySort(int arr[], int len, int k){int left = 0;int right = len - 1;int mid = 0;while(left mid = left + (right - left) / 2;if(arr[mid]  k){right = mid - 1;}else if(arr[mid]  

      揭晓答案的时刻: O ( l o g N ) O(logN) O(logN)

      为什么呢?上面代码为二分查找,每次查找范围缩减一半。在最坏的情况下,要一直缩减到rightif(N if(N

上一篇:国产服务器厂商怎么选?

下一篇:轻量云服务器怎么设置?