探索数据结构:解锁计算世界的密码


✨✨ 欢迎大家来到贝蒂大讲堂✨✨

🎈🎈养成好习惯,先赞后看哦~🎈🎈

所属专栏:数据结构与算法
贝蒂的主页:Betty‘s blog

前言

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

1. 什么是数据结构

数据结构(Data Structure)是计算机存储、组织数据的方式,指相互之间存在一种或多种特定关系的数据元素的集合。

下标是常见的数据结构:

名称 定义
数组(Array) 数组是一种聚合数据类型,它是将具有相同类型的若干变量有序地组织在一起的集合。
链表(Linked List) 链表是一种数据元素按照链式存储结构进行存储的数据结构,这种存储结构具有在物理上存在非连续的特点。
栈(Stack) 栈是一种特殊的线性表,它只能在一个表的一个固定端进行数据结点的插入和删除操作
队列(Queue) 队列和栈类似,也是一种特殊的线性表。和栈不同的是,队列只允许在表的一端进行插入操作,而在另一端进行删除操作。
树(Tree) 树是典型的非线性结构,它是包括,2 个结点的有穷集合 K
堆(Heap) 堆是一种特殊的树形数据结构,一般讨论的堆都是二叉堆。
图(Graph) 图是另一种非线性数据结构。在图结构中,数据结点一般称为顶点,而边是顶点的有序偶对

2. 什么是算法

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

算法一般分为:排序,递归与分治,回溯,DP,贪心,搜索算法

  • 算法往往数学密切相关,就如数学题一样,每道数学题都有不同的解法,算法也是同理。

3. 复杂度分析

3.1 算法评估

我们在进行算法分析时,常常需要完成两个目标。一个是找出问题的解决方法,另一个就是找到问题的最优解。而为了找出最优解,我们就需要从两个维度分析:

  • 时间效率:算法运行的快慢
  • 空间效率:算法所占空间的大小

3.2 评估方法

评估时间的方法主要分为两种,一种是实验分析法,一种是理论分析法

(1) 实验分析法

实验分析法简单来说就是将不同种算法输入同一台电脑,统计时间的快慢。但是这种方法有两大缺陷:

  1. 无法排查实验自身条件与环境的条件的影响:比如同一种算法在不同配置的电脑上的运算速度可能完全不同,甚至结果完全相反。我们很难排查所有情况。
  2. 成本太高:同一种算法可能在数据少时表现不明显,在数据多时速率较快

(2) 理论分析法

由于实验分析法的局限性,就有人提出了一种理论测评的方法,就是渐近复杂度分析(asymptotic complexity analysis),简称复杂度分析

这种方法体现算法运行所需的时间(空间)资源与输入数据大小之间的关系,能有效的反应算法的优劣。

4. 时间复杂度与空间复杂度

4.1 时间复杂度

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

为了准确的表述一段代表所需时间,我们先假设赋值(=)与加号(+)所需时间为1ns,乘号(×)所需时间为2ns,打印所需为3ns。

让我们计算如下代码所需总时间:

int main()
{
	int i = 1;//1ns
	int n = 0;//1ns
	scanf("%d", &n);
	for (i = 0; i < n; i++)
	{
		printf("%d ", i);//3ns
	}
	return 0;
}

计算时间如下:
$$
T(n)=1+1+3×n=3n+2
$$

但是实际上统计每一项所需时间是不现实的,并且由于是理论分析,当n—>∞时,其余项皆可忽略,T(n)的数量级由最高阶决定。所以我们计算时间复杂度时,可以简化为两个步骤:

  1. 忽略除最高阶以外的所有项。
  2. 忽略所有系数。

而上述代码时间可以记为O(n),这种方法被称为大O的渐进表示法。如果计算机结果全是常数,则记为O(1)。

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

4.2 空间复杂度

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

让我们计算一下冒泡排序的空间复杂度

// 计算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;
	}
}
  • 通过观察我们可以看出,冒泡排序并没有开辟多余的空间,所以空间复杂度为O(1).

5. 复杂度分类

算法的复杂度有几个量级,表示如下:
$$
O(1) < O( log N) < O(N) < O(Nlog N) < O(N 2 ) < O(2^𝑛 ) < 𝑂(O!)
$$

  • 从左到右复杂度依次递增,算法的缺点也就越明显

图示如下:

5.1 常数O(1)阶

常数阶是一种非常快速的算法,但是在实际应用中非常难实现

以下是一种时间复杂度与空间复杂度皆为O(1)的算法:

int main()
{
	int a = 0;
	int b = 1;
	int c = a + b;
	printf("两数之和为%d\n", c);
	return 9;
}

5.2 对数阶O(logN)

对数阶是一种比较快的算法,它一般每次减少一半的数据。我们常用的二分查找算法的时间复杂度就为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 {	//既不在左边,也不在右边,那就是找到答案了
            return middle;
        }
    }
    //没有找到目标值
    return -1;
}

空间复杂度为O(logN)的算法,一般为分治算法

比如用递归实现二分算法:

int binary_search(int ar[], int low, int high, int key)
{
    if(low > high)//查找不到
        return -1;
    int mid = (low+high)/2;
    if(key == ar[mid])//查找到
        return mid;
    else if(key < ar[mid])
        return Search(ar,low,mid-1,key);
    else
        return Search(ar,mid+1,high,key);
}

每一次执行递归都会对应开辟一个空间,也被称为栈帧

5.3 线性阶O(N)

线性阶算法,时间复杂度与空间复杂度随着数量均匀变化。

遍历数组或者链表是常见的线性阶算法,以下为时间复杂度为O(N)的算法:

int main()
{
	int n = 0;
	int count = 0;
	scanf("%d", &n);
	for (int i = 0; i < n; i++)
	{
		count += i;//计算0~9的和
	}
	return 0;
}

以下为空间复杂度为O(N)的算法

int main()
{
	int n = 0;
	int count = 0;
	scanf("%d", &n);
	int* p = (int*)malloc(sizeof(int) * n);
	//开辟大小为n的空间
	if (p == NULL)
	{
		perror("malloc fail");
		return -1;
          }
       free(p);
       p=NULL;
	return 0;
}

5.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);
	}
}

空间复杂度为O(NlogN)的算法,最常见的莫非归并排序

void Merge(int sourceArr[],int tempArr[], int startIndex, int midIndex, int endIndex){
    int i = startIndex, j=midIndex+1, k = startIndex;
    while(i!=midIndex+1 && j!=endIndex+1) {
        if(sourceArr[i] > sourceArr[j])
            tempArr[k++] = sourceArr[j++];
        else
            tempArr[k++] = sourceArr[i++];
    }
    while(i != midIndex+1)
        tempArr[k++] = sourceArr[i++];
    while(j != endIndex+1)
        tempArr[k++] = sourceArr[j++];
    for(i=startIndex; i<=endIndex; i++)
        sourceArr[i] = tempArr[i];
}
 
//内部使用递归
void MergeSort(int sourceArr[], int tempArr[], int startIndex, int endIndex) {
    int midIndex;
    if(startIndex < endIndex) {
        midIndex = startIndex + (endIndex-startIndex) / 2;//避免溢出int
        MergeSort(sourceArr, tempArr, startIndex, midIndex);
        MergeSort(sourceArr, tempArr, midIndex+1, endIndex);
        Merge(sourceArr, tempArr, startIndex, midIndex, endIndex);
    }
}

5.5 平方阶O(N2)

平方阶与线性对数阶相似,常见于嵌套循环中,每层循环的复杂度为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;
	}
}

计算过程如下;
$$
T(N)=1+2+3+......+n-1=(n2-n)/2=O(n2)
$$

空间复杂度为O(N2),最简单的就是动态开辟。

{
	int n = 0;
	int count = 0;
	scanf("%d", &n);
	int* p = (int*)malloc(sizeof(int) * n*n);
	//开辟大小为n的空间
	if (p == NULL)
	{
		perror("malloc fail");
		return -1;
          }
       free(p);
       p=NULL;
	return 0;
}

5.6 指数阶O(2N)

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

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

int Fib1(int n)
{
	if (n == 1 || n == 2)
	{
		return 1;
	}
	else
	{
		return Fib1(n - 1) + Fib1(n - 2);
	}
}

粗略估计
$$
T(n)=20+21+22+.....+2(n-1)=2n-1=O(2N)
$$

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

空间复杂度为O(2N)的算法一般与树有关,比如建立满二叉树

TreeNode* buildTree(int n) {
	if (n == 0)
		return NULL;
	TreeNode* root = newTreeNode(0);
	root->left = buildTree(n - 1);
	root->right = buildTree(n - 1);
	return root;
}

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

示意图:

  • 空间复杂度为阶乘阶O(N!)的算法并不常见,这里就不在一一列举。

本文由博客一文多发平台 OpenWrite 发布!

热门相关:混在三国当军阀   士子风流   明朝好丈夫   玉堂金闺   护花猎王