探索数据结构:入门及复杂度的解锁

简介: 探索数据结构:入门及复杂度的解锁

前言

随着应用程序变得越来越复杂和数据越来越丰富,几百万、几十亿甚至几百亿的数据就会出现,而对这么大对数据进行搜索、插入或者排序等的操作就越来越慢,人们为了解决这些问题,提高对数据的管理效率,提出了一门学科即:数据结构与算法


1. 什么是数据结构

数据结构(Data Structure)是计算机存储、组织数据的方式,指相互之间存在一种或多种特定关系的数据元素的集合,它涉及到如何组织和存储数据,以便在程序中进行高效的访问和操作。


数据结构的基本类型:

数据结构类型

名称 定义
数组(Array) 一组连续的内存空间,用来存储相同类型的数据。
链表(Linked List) 由一系列节点组成,每个节点包含数据和指向下一个节点的指针。
栈(Stack) 一种后进先出的数据结构。
队列(Queue) 一种先进先出的数据结构。
树(Tree) 由节点和边组成的层级结构。每个节点可以有任意数量的子节点。树的最顶层节点称为根节点,没有子节点的节点称为叶子节点。
堆(Heap) 一种完全二叉树的结构。每个节点的值都小于等于(或大于等于)其子节点的值。
图(Graph) 由节点和边组成的非线性结构。节点之间可以有多条边相连。可以用来表示网络、地图等复杂结构。
哈希表(Hash Table) 一种通过哈希函数将关键字映射到表中位置的数据结构。


不同的数据结构适用于不同的场景,选择合适的数据结构可以提高程序的效率。

2. 什么是算法

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


常见的算法有:


  1. 排序算法(Sorting Algorithm):将一组数据按照一定规则进行排序,如冒泡排序、选择排序、插入排序、快速排序等。
  2. 查找算法(Search Algorithm):在一个有序的数据集中查找指定的数据,如二分查找、线性查找等。
  3. 递归算法(Recursion Algorithm):通过函数自身的调用实现对问题的解决,如斐波那契数列、阶乘等。
  4. 动态规划算法(Dynamic Programming Algorithm):通过将问题分解成更小的子问题来解决复杂问题,如背包问题、最长公共子序列等。
  5. 贪心算法(Greedy Algorithm):每次选择局部最优解来解决问题,如最小生成树算法、最短路径算法等。


3. 数据结构和算法的重要性

  1. 高效解决问题:数据结构和算法可以帮助我们更有效地解决各种问题,包括排序、搜索、图形遍历等。通过使用合适的数据结构和算法,我们可以大大提高计算效率,节省时间和空间资源。
  2. 可扩展性:随着计算机硬件和软件的发展,我们需要处理的问题变得越来越复杂。数据结构和算法提供了一种可扩展的方法来应对这些挑战,使得我们能够更好地适应不断变化的需求。
  3. 优化程序性能:对于需要大量计算的应用程序,优化程序性能至关重要。数据结构和算法可以帮助我们减少不必要的计算,提高程序运行速度,从而提高用户体验。
  4. 提高代码质量:使用适当的数据结构和算法可以确保我们的代码更加简洁、易于理解和维护。这有助于提高代码质量,降低出错概率,并为团队协作创造更好的环境。
  5. 适用于各种领域:数据结构和算法不仅在计算机科学领域具有重要意义,而且在其他领域也发挥着关键作用。例如,在金融、医疗、物流等领域,高效的数据处理方法同样具有重要价值。


一、算法效率的衡量

那么提到算法效率,我们肯定想知道如何衡量一个算法的好坏?

例如以下代码:

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

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


算法在编写成可执行程序后,运行时需要耗费时间资源和空间(内存)资源 。因此衡量一个算法的好坏,一般是从时间和空间两个维度来衡量的,即时间复杂度和空间复杂度。如果你不知道什么是复杂度时,你可能就无法正确的完成题目。因此,我们在学习数据结构与算法的第一步,就是要理解什么是复杂度。


  • 时间复杂度主要衡量的是一个算法的运行速度。由于在不同的硬件上,程序运行的速度会有所不同,所以时间复杂度代表的并不是一个程序运行的时间,这并没有意义。而一个算法所花费的时间与其中语句的执行次数成正比,因此我们把算法中的基本操作的执行次数,称为算法的时间复杂度。
  • 空间复杂度主要衡量一个算法所需要的额外空间。正如时间复杂度计算的不是时间,空间复杂度也不是计算程序占用了多少bytes的空间,因为这个也没太大意义,空间复杂度算的是变量的个数。

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


二、时间复杂度

2.1 什么是时间复杂度

一个算法所花费的时间与其中语句的执行次数成正比例,算法中的基本操作的执行次数,为算法的时间复杂度。

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

然我们看一道题目:

// 请计算一下Func1基本操作执行了多少次?
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);
}


我们通过分析得到Func1 执行的基本操作次数如下:

N = 10 ,F(N) = 130

N = 100 ,F(N) = 10210

N = 1000 ,F(N) = 1002010


显然如果直接用来表示时间复杂度的话会显得太过复杂。实际上我们发现随之N的不断增大,F(N)后续两项对结果的影响越来越小。因此我们在计算时间复杂度时,并不一定要计算精确的执行次数,只需求大概的执行次数,因此,就有了大O渐进表示法。

2.2 大O的渐进表达法


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

推导大O阶方法:

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


计算复杂度时,有时候会出现不同情况的结果,这时应该以最坏的结果考虑

例如上述代码的时间复杂度就是O( ), 就是我们求得的大O阶。我们用O( )表示当N趋于无穷大时,Func1()算法执行基本操作的次数约为 次(后两项忽略不计)。


几个小例子:


------------------------------------------------>>>  O( )


------------------------------------------->>>  O( )


-------------------------->>>  O( )



2.3 一些常见的复杂度

我们常见的复杂度有以下几种:

第一级:O(1),O(logn)

第二级:O(n),O(nlogn)

第三级:O( ),O( ),O(n!)

从上往下,从左到右,算法效率依次降低,下图为各种复杂度对于n的变化曲线:

实例1(O(1)):

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

操作执行了10次->O(10)

通过推导大O阶方法,常数的时间复杂度为 O(1)


实例2(O(logN)):

对数阶是一种比较快的算法,它一般每次减少一半的数据。我们常用的二分查找算法的时间复杂度就为O(logN)

// 计算BinarySearch的时间复杂度?
int BinarySearch(int* a, int n, int x)
{
    assert(a);
    int begin = 0;
    int end = n-1;
 // [begin, end]:begin和end是左闭右闭区间,因此有=号
    while (begin <= end)
    {
        int mid = begin + ((end-begin)>>1);
        if (a[mid] < x)
            begin = mid+1;
        else if (a[mid] > x)
            end = mid-1;
        else
            return mid;
    }
    return -1;
}

最好1次,

最坏log2(n)次,

时间复杂度为 O(logN)

第几次查询 剩余待查询元素数量
1 N/2
2 N/(2^2)
3 N/(2^3)
N N/(2^N)

ps:为何是logN 而不是log2 (N)

假如有logaB(a为底数),由换底公式可得:

logcA(c为底数)为常数,

由O的运算规则"O( C × f(N) )=O( f(N ) ),其中C是一个正的常数,得O(logaB)=O(logcB)

可知算法的时间复杂度与不同底数只有常数的关系,均可以省略自然可以用logN代替。

实例3(O(N)):

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

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


实例4(O(NlogN)):

无论是时间复杂度还是空间复杂度,线性对数阶一般出现在嵌套循环中,即一层的复杂度为O(N),另一层为O(logN)

比如说循环使用二分查找打印:

int binary_search(int nums[], int size, int target) //nums是数组,size是数组的大小,target是需要查找的值
{
    int left = 0;
    int right = size - 1; // 定义了target在左闭右闭的区间内,[left, right]
    while (left <= right) { //当left == right时,区间[left, right]仍然有效
        int middle = left + ((right - left) / 2);//等同于 (left + right) / 2,防止溢出
        if (nums[middle] > target) {
            right = middle - 1; //target在左区间,所以[left, middle - 1]
        }
        else if (nums[middle] < target) {
            left = middle + 1;  //target在右区间,所以[middle + 1, right]
        }
        else {  //既不在左边,也不在右边,那就是找到答案了
            printf("%d ", nums[middle]);
        }
    }
    //没有找到目标值
    return -1;
}
void func(int nums[], int size, int target)
{
  for (int i = 0; i < size; i++)
  {
    binary_search(nums, size, target);
  }
}


实例5(O( )):

平方阶与线性对数阶相似,常见于嵌套循环中,每层循环的复杂度为O(N)

时间复杂度为O(N2),最常见的就是冒泡排序

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


实例6(O( )):

指数阶的算法效率低,并不常用。

常见的时间复杂度为O(2N)的算法就是递归实现斐波拉契数列:

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


  • 值得一提的是斐波拉契的空间复杂度为O(N),因为在递归至最深处后往回归的过程中,后续空间都在销毁的空间上建立的,这样能大大提高空间的利用率。


实例7(O(N!)):

阶乘阶的算法复杂度最高,几乎不会采用该类型的算法。

这是一个时间复杂度为阶乘阶O(N!)的算法

int func(int n)
{
  if (n == 0)
    return 1;
  int count = 0;
  for (int i = 0; i < n; i++) 
  {
    count += func(n - 1);
  }
  return count;
}


三、空间复杂度

空间复杂度也是一个数学表达式,是对一个算法在运行过程中临时占用存储空间大小的量度


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

// 计算Fibonacci的空间复杂度?
 
long long* Fibonacci(int 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;
}


上面说到空间复杂度是统计变量的个数,因此通过分析得到Fibonacci() 创建的变量个数为:


                                                 F(n)=n+1+1

其中,n+1为malloc在堆上申请的空间,1为在栈上开辟的空间i(此处我们不考虑形参)。与时间复杂度相同,为了表达方便,空间复杂度同样采用大O的渐进表示法,通过保留最高项,去除常数项,我们得到Fibonacci()函数的空间复杂度为O(n)。

四、总结

1.时间复杂度计算的是基本操作执行次数,空间复杂度计算的是变量的个数,二者都采用大O渐进表示法。

2.时间/空间复杂度都是在最坏情况下所得到的。

3.时间一去不复返,是累积的;而空间是可以释放并重复利用的,是不累积的。

相关文章
|
2月前
|
算法
数据结构(复杂度)
数据结构(复杂度)
23 0
|
2月前
|
存储 缓存 应用服务中间件
Nginx入门 -- 基本数据结构中之ngx_hash_t
Nginx入门 -- 基本数据结构中之ngx_hash_t
36 0
|
2月前
|
存储 缓存 应用服务中间件
Nginx入门 -- 基本数据结构中之ngx_list_t,ngx_queue_t
Nginx入门 -- 基本数据结构中之ngx_list_t,ngx_queue_t
28 0
|
2月前
|
存储 应用服务中间件 nginx
Nginx入门 -- 基本数据结构中之ngx_str_t,ngx_array_t
Nginx入门 -- 基本数据结构中之ngx_str_t,ngx_array_t
71 0
|
4月前
|
机器学习/深度学习 存储 算法
【初阶数据结构篇】时间(空间)复杂度
复杂度是计算机科学中的一个基础概念,它帮助我们理解和评估算法的效率,对于算法设计和优化至关重要。
46 2
【初阶数据结构篇】时间(空间)复杂度
|
4月前
|
算法
【初阶数据结构】复杂度算法题篇
该方法基于如下的事实:当我们将数组的元素向右移动 k 次后,尾部 kmodn 个元素会移动至数组头部,其余元素向后移动 kmodn 个位置。
28 1
|
4月前
|
应用服务中间件 nginx C语言
Nginx入门 -- 基本数据结构中之ngx_str_t,ngx_array_t
这两种数据结构是Nginx自定义数据类型的例子,它们证明了Nginx设计者在构建一个为高并发和高性能优化的web服务器时的精确和高效。理解这些数据结构是深入学习Nginx内部机制的基础,同时也是扩展和开发Nginx模块不可或缺的一部分知识。
43 1
|
5月前
|
机器学习/深度学习 存储 算法
【数据结构】算法的复杂度
算法的时间复杂度和空间复杂度
77 1
【数据结构】算法的复杂度
|
5月前
|
算法 数据挖掘 计算机视觉
Python并查集实战宝典:从入门到精通,让你的数据结构技能无懈可击!
【7月更文挑战第17天】并查集,如同瑞士军刀,是解决元素分组问题的利器,应用于好友关系、像素聚类、碰撞检测和连通性分析等场景。本文从基础到实战,介绍并查集的初始化、查找与路径压缩、按秩合并,以及在Kruskal算法中的应用。通过并查集,实现高效动态集合操作,对比哈希表和平衡树,其在合并与查找上的性能尤为突出。学习并查集,提升算法解决复杂问题的能力。
84 5
|
4月前
|
存储 算法
【数据结构】复杂度(长期维护)
【数据结构】复杂度(长期维护)