C语言数据结构之算法的时间复杂度

2024-09-27 18:25:35

1、算法的复杂度

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

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

2、时间复杂度

2.1 时间复杂度的定义

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

举例：

请计算一下Func1中++count语句总共执行了多少次？

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

时间复杂度函数：F(N)=N*N+2*N+10

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

2.2 大O的渐进表示法

大O符号（Big O notation）：是用于描述函数渐进行为的数学符号

1、用1来代替常数,F(N)函数只有常数 O(1)
2、在运行次数中，只保留最高阶。 F(N)=N^3+N^2 --> O(N^3)
3、最高项系数化为1。F(N) = 2*N --> O(N)

注：复杂度不固定时，时间复杂度看的是最坏的情况（悲观的估算）

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

最好情况：1次找到
最坏情况：N次找到
平均情况：N/2次找到

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

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

3.1 冒泡排序的时间复杂度

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

经分析的：F(N)= O(N^2)

3.2 二分查找的时间复杂度

//左闭右开
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;
}

//左闭右闭
int BinarySearch(int* a, int n, int x)
{
assert(a);
int begin = 0;
int end = n-1;
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;
}

假设找了x次：

1*2*2*2*2......*2 = N

2^x = N

x = log2 N

最坏：O(log2 N) 简写成 log(N)

3.3 阶乘(递归)的时间复杂度

1、每次函数调用是O(1),那么就要看他的递归次数。
2、每次函数调用不是O(n),那么就看他的递归调用中次数的累加。

long long Fac(size_t N)
{
if (0 == N)
return 1;
return Fac(N - 1) * N;
}

F(N) = O(N)

3.4菲波那切数列的时间复杂度

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

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

到此这篇关于C语言数据结构之算法的时间复杂度的文章就介绍到这了,更多相关c语言算法内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！

C语言数据结构与算法之时间空间复杂度入门

目录数据结构与算法什么是数据结构?什么是算法? 分析维度大O的渐进表示法常数阶线性阶对数阶其他时间复杂度指标空间复杂度数据结构与算法终于开始搞这块难啃的骨头了,走上这条漫漫长路之前要明白: 什么是数据结构?什么是算法? 是数据之间存在一种或多种特定关系的数据元素集合,为编写出一个“好”的程序,必须分析待处理对象的特性及各处理对象之间存在的关系,这也就是研究数据结构的意义所在为编写出一个“好”的程序,必须分析待处理对象的特性及各处理对象之间存在的关系这也就是研究数据结构的意义所
C语言数据结构与算法时间空间复杂度基础实践

目录小感想时间复杂度空间复杂度小感想今天去看了看许多人今年去各个大厂面试的面经,确实如大体所说,各大公司越来越注重性能迭代,时代需要数据结构与算法这样的考试. 一个公司的成本主要来自于人力成本,但是上了规模写核心代码的人少了,成本就会来自于机器,资源,时间,抢占到这些就相当于无时无刻在减少客户流失.所以同样一段代码给两个人写,甲拿 8000,乙拿 25000,但是后者效率提高了50%,而这50%带来的收益远远超过了(25000-8000),这就是为什么许多大厂要给出如此吸引人的高薪资来
C语言数据结构之算法的时间复杂度

目录 1.算法的复杂度 2.时间复杂度 2.1 时间复杂度的定义 2.2 大O的渐进表示法 3.常见时间复杂度计算举例 3.1 冒泡排序的时间复杂度 3.2 二分查找的时间复杂度 3.3 阶乘(递归)的时间复杂度 3.4菲波那切数列的时间复杂度 1.算法的复杂度算法在编写成可执行程序后,运行时需要耗费时间资源和空间(内存)资源 .因此衡量一个算法的好坏,一般是从时间和空间两个维度来衡量的,即时间复杂度和空间复杂度. 时间复杂度主要衡量一个算法的运行快慢,而空间复杂度主要衡量一个算法运行所需要的
C语言数据结构与算法之排序总结(二)

目录一.前言二.选择类排序 1.简单选择排序 2.树形选择排序 3.堆选择排序三.归并排序四.分配类排序 1.多关键字排序 2.链式基数排序五.总结归纳一.前言之前的排序总结(一)对插入类和交换类排序作了比较详细的总结,对于直接插入.希尔排序.冒泡排序.快速排序要求熟练掌握这篇排序全面总结(二)主要介绍选择类排序中的简单.树形和堆排序,归并排序.分配类排序的基数排序二.选择类排序选择类:每次从待排序的无序序列中,选择一个最大或最小的数字,放到前面,数据元素为空时排序结束 1.
C语言数据结构与算法之排序总结(一)

目录一.前言二.基本概念 1.排序 2.排序方法的稳定性 3.内部和外部排序三.插入类排序 1.直接插入排序 2.折半插入排序 3.希尔排序四.交换类排序 1.冒泡排序 2.快速排序五.总结比较一.前言学习目标: 排序和查找密不可分,将待处理的数据按关键值大小有序排列后,查找更加快速准确理解各种排序算法的定义和特点,并能将代码灵活运用掌握各种排序方法时间复杂度与空间复杂度理解排序稳定和不稳定的概念重点和难点: 希尔.快速.堆.归并排序这几种快
C语言数据结构与算法之图的遍历(二)

目录前言广度优先搜索过程主要思想代码实现前言在上一章的内容中我们使用了深度优先搜索来进行遍历,这一章我们选择使用广度优先搜索来完成这个图的遍历 --> 结果如下: 广度优先搜索过程使用广度优先搜索来遍历这个图的过程如下. 首先以一个未被访问过的顶点作为起始顶点,比如以1号点作为起始顶点. 将1号点放到队列中,然后将与1号点相邻的未访问过的顶点即 2,3,5号顶点依次放入队列中,如下图: 接下来将2号顶点相邻的未访问过的顶点4号放入到队列中.到此所有的顶点都访问过了,遍历
C语言数据结构与算法之图的遍历

目录引入深度优先搜索代码实现完整代码引入在数据结构中常见的有深度优先搜索和广度优先搜索.为什么叫深度和广度呢?其实是针对图的遍历而言的,请看下面这个图: 图是由一些小圆点(称为顶点) 和连接这些点的直线 (称为边)组成的. 例如上图就是由5个顶点(编号为 1,2,3,4,5) 和5条边(1-2,1-3,1-4,2-4)组成. 现在我们从1号顶点开始遍历这个图,遍历就是把图的每一个顶点都访问一次.使用深度优先搜索将会得到如下的结果. 图中每个顶点旁边的数表示这个顶点是第几个
C语言数据结构与算法之链表(二)

目录引入模拟链表介绍插入代码实现代码实现引入在上一节的学习中我们介绍了C语言如何实现链表,但是,在这一章,我们将抛开令人头秃的指针和结构体,我们将另外使用一种数组来实现的方式,叫做模拟链表.让我们一起来看看. 模拟链表介绍链表中的每一个结点都只有两个部分. 我们可以使用一个数组date来储存每序列中的每一个数.那每一个数右边的数是谁,这一点该如何解决呢?在上一章的内容中我们是使用指针来解决的,这里我们只需再用一个数组right来存放序列中每一个数右边的数是谁就可以了.具体要怎么
C语言数据结构与算法之链表(一)

目录引言链表的相关思考链表结点结构建立链表实现插入操作完整代码引言在存储一大波数的时候,我们通常使用的是数组,但是数组有时候又会显得不够灵活,比如下面这个例子: 有一串已经排序好的数 2,3,5,8,9 ,10 如果我们想要往数组中插入6 这个元素,需要把 8 以后的元素全部往后挪一位这样操作显然很耗费时间,如果使用链表的话则会快很多.那么什么是链表呢?请看下图: 此时如果需要在8前面加入一个6,那么只需要向下图一样更改一下就可以了,而不用向像最开始那样把每个数向后挪. 链表的
C语言数据结构与算法之单链表

目录基本概念读取数据元素获取第i个结点的数据元素插入数据元素初始化链表打印链表顺序表查空顺序表的删除删除第i个结点及其数据元素情况1:当删除的是第一个元素情况2:除第一个结点外完整代码删除单链表整表单链表VS顺序表基本概念链表的每一个结点中只包含一个指针域优点 : 储存空间利用高效举例来说: typedef struct student{ int id; //学生编号 char* name; //学生名称 //指向下一结点的指针 struct Studen