数据结构入门 时间 空间复杂度解析

简介: 数据结构入门 时间 空间复杂度解析

一. 算法效率

算法效率分析分为两种:第一种是时间效率,第二种是空间效率。

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


总结经过这么久技术的发展 我们对于时间复杂度的要求高于空间复杂度的要求


二. 时间复杂度

2.1 时间复杂度的概念

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

2.2 大O的渐进表示法

我们直接上题目

// 请计算一下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);
}

这里经过我们的计算发现实际次数我们可以用一个函数表达F(n) = n^2+2*n+10


当我们的n等于10的时候 它的次数是130


放我们的n是100的时候 它的次数是10210


当我们的n是1000的时候 它的次数是1002010


我们可以发现 它执行的次数实际上只跟n的平方有强相关性


这个时候我们只需要了解到这个程序的最高次项 我们就能估算出这个程序所需要运行的数量级


那么这里就能够引生出我们的大O的渐进表示法


推导大O阶方法:

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


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


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


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


当n等于10的时候 它运行的次数就是100


当n等于100的时候 它运行的次数就是10000


当n等于1000的时候 它运行的次数就是1000000


此外 如果说随着我们输入的不同空间复杂度也有所改变的话 那么我们取最坏的空间复杂度作为我们的复杂度

2.3 题目练习

题目一
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)

题目二
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);
}

它的计算的次数是 M+N次

实际的空间复杂度就是O(max(M,N))

题目三
void Func4(int N) {
  int count = 0;
  for (int k = 0; k < 100; ++k) {
    ++count;
  }
  printf("%d\n", count);
}

这里实际上和N没有关系 它会计算100次

所以说它的次数是一个常数

常数的时间复杂度是O(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;
    }
}

这里实际运行的次数是end的平方-n之后除以2

所以说 它的时间复杂度是O(N^2)

题目五
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;
        else
            return mid;
    }
    return -1;
}

它最好的运算情况是一次

运算最坏的情况是logN

所以说它的时间复杂度是logN

题目六
long long Factorial(size_t N) {
return N < 2 ? N : Factorial(N-1)*N; }

实际上它的它的空间复杂度是O(N)

题七
long long Fibonacci(size_t N) {
return N < 2 ? N : Fibonacci(N-1)+Fibonacci(N-2);
}

实际上它的复杂度是 2的0次方加上2的一次放+…+2的N-1次方减去N


实际上它的它的空间复杂度是O(2^N)


实例答案及分析:

实例1基本操作执行了2N+10次,通过推导大O阶方法知道,时间复杂度为 O(N)

实例2基本操作执行了M+N次,有两个未知数M和N,时间复杂度为 O(N+M)

实例3基本操作执行了10次,通过推导大O阶方法,时间复杂度为 O(1)

实例4基本操作执行最好1次,最坏N次,时间复杂度一般看最坏,时间复杂度为 O(N)

实例5基本操作执行最好N次,最坏执行了(N*(N+1)/2次,通过推导大O阶方法+时间复杂度一般看最坏,时间复杂度为 O(N^2)

实例6基本操作执行最好1次,最坏O(logN)次,时间复杂度为 O(logN) ps:logN在算法分析中表示是底数为2,对数为N。有些地方会写成lgN。(建议通过折纸查找的方式讲解logN是怎么计算出来的)

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

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


三. 空间复杂度

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

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

实际上冒泡排序并没有占用额外的空间

所以说它使用的空间是常量级别的

所以说它的空间复杂度是O(1)

题目二
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 ;
}

这里用来计算fib数 开辟了n+1个空间

实际上的空间复杂度是O(N)

题目三
long long Factorial(size_t N) {
 return N < 2 ? N : Factorial(N-1)*N; }

它实际上开辟了N到1数量的空间

所以说它的空间复杂度是O(N)

但是有的同学会认为这个跟时间复杂度一样是O(N^2)

实际上这里我们要明确一点

时间是不能复用的
空间是可以复用的


以上便是本文所有内容了,如有错误请各位大佬不吝赐教,感谢留言

目录
相关文章
|
6月前
|
Web App开发 移动开发 前端开发
React音频播放器样式自定义全解析:从入门到避坑指南
在React中使用HTML5原生&lt;audio&gt;标签时,开发者常面临视觉一致性缺失、样式定制局限和交互体验割裂等问题。通过隐藏原生控件并构建自定义UI层,可以实现完全可控的播放器视觉风格,避免状态不同步等典型问题。结合事件监听、进度条拖拽、浏览器兼容性处理及性能优化技巧,可构建高性能、可维护的音频组件,满足跨平台需求。建议优先使用成熟音频库(如react-player),仅在深度定制需求时采用原生方案。
202 12
|
7月前
|
存储 索引 Python
Python入门:6.深入解析Python中的序列
在 Python 中,**序列**是一种有序的数据结构,广泛应用于数据存储、操作和处理。序列的一个显著特点是支持通过**索引**访问数据。常见的序列类型包括字符串(`str`)、列表(`list`)和元组(`tuple`)。这些序列各有特点,既可以存储简单的字符,也可以存储复杂的对象。 为了帮助初学者掌握 Python 中的序列操作,本文将围绕**字符串**、**列表**和**元组**这三种序列类型,详细介绍其定义、常用方法和具体示例。
Python入门:6.深入解析Python中的序列
|
6月前
|
Java 关系型数据库 数据库连接
Javaweb之Mybatis入门程序的详细解析
本文详细介绍了一个MyBatis入门程序的创建过程,从环境准备、Maven项目创建、MyBatis配置、实体类和Mapper接口的定义,到工具类和测试类的编写。通过这个示例,读者可以了解MyBatis的基本使用方法,并在实际项目中应用这些知识。
140 11
|
7月前
|
存储 Linux iOS开发
Python入门:2.注释与变量的全面解析
在学习Python编程的过程中,注释和变量是必须掌握的两个基础概念。注释帮助我们理解代码的意图,而变量则是用于存储和操作数据的核心工具。熟练掌握这两者,不仅能提高代码的可读性和维护性,还能为后续学习复杂编程概念打下坚实的基础。
Python入门:2.注释与变量的全面解析
|
6月前
|
移动开发 前端开发 JavaScript
从入门到精通:H5游戏源码开发技术全解析与未来趋势洞察
H5游戏凭借其跨平台、易传播和开发成本低的优势,近年来发展迅猛。接下来,让我们深入了解 H5 游戏源码开发的技术教程以及未来的发展趋势。
|
10月前
|
C语言
【数据结构】栈和队列(c语言实现)(附源码)
本文介绍了栈和队列两种数据结构。栈是一种只能在一端进行插入和删除操作的线性表,遵循“先进后出”原则;队列则在一端插入、另一端删除,遵循“先进先出”原则。文章详细讲解了栈和队列的结构定义、方法声明及实现,并提供了完整的代码示例。栈和队列在实际应用中非常广泛,如二叉树的层序遍历和快速排序的非递归实现等。
834 9
|
10月前
|
存储 算法
非递归实现后序遍历时,如何避免栈溢出?
后序遍历的递归实现和非递归实现各有优缺点,在实际应用中需要根据具体的问题需求、二叉树的特点以及性能和空间的限制等因素来选择合适的实现方式。
210 59
|
3月前
|
编译器 C语言 C++
栈区的非法访问导致的死循环(x64)
这段内容主要分析了一段C语言代码在VS2022中形成死循环的原因,涉及栈区内存布局和数组越界问题。代码中`arr[15]`越界访问,修改了变量`i`的值,导致`for`循环条件始终为真,形成死循环。原因是VS2022栈区从低地址到高地址分配内存,`arr`数组与`i`相邻,`arr[15]`恰好覆盖`i`的地址。而在VS2019中,栈区先分配高地址再分配低地址,因此相同代码表现不同。这说明编译器对栈区内存分配顺序的实现差异会导致程序行为不一致,需避免数组越界以确保代码健壮性。
35 0
栈区的非法访问导致的死循环(x64)
232.用栈实现队列,225. 用队列实现栈
在232题中,通过两个栈(`stIn`和`stOut`)模拟队列的先入先出(FIFO)行为。`push`操作将元素压入`stIn`,`pop`和`peek`操作则通过将`stIn`的元素转移到`stOut`来实现队列的顺序访问。 225题则是利用单个队列(`que`)模拟栈的后入先出(LIFO)特性。通过多次调整队列头部元素的位置,确保弹出顺序符合栈的要求。`top`操作直接返回队列尾部元素,`empty`判断队列是否为空。 两题均仅使用基础数据结构操作,展示了栈与队列之间的转换逻辑。
|
8月前
|
存储 C语言 C++
【C++数据结构——栈与队列】顺序栈的基本运算(头歌实践教学平台习题)【合集】
本关任务:编写一个程序实现顺序栈的基本运算。开始你的任务吧,祝你成功!​ 相关知识 初始化栈 销毁栈 判断栈是否为空 进栈 出栈 取栈顶元素 1.初始化栈 概念:初始化栈是为栈的使用做准备,包括分配内存空间(如果是动态分配)和设置栈的初始状态。栈有顺序栈和链式栈两种常见形式。对于顺序栈,通常需要定义一个数组来存储栈元素,并设置一个变量来记录栈顶位置;对于链式栈,需要定义节点结构,包含数据域和指针域,同时初始化栈顶指针。 示例(顺序栈): 以下是一个简单的顺序栈初始化示例,假设用C语言实现,栈中存储
322 77

推荐镜像

更多
  • DNS