数据结构与算法学习笔记之 复杂度分析

简介: 前言:   大家都知道数据结构和英语,就如同程序员的两条腿一样;只有不断的积累,学习,拥有了健壮的“双腿”才能越走越远;在数据结构和算法的领域,不得不承认自己就是一只菜鸟;需要不断的学习;在学习过程中,经常会有一些自己的看法,和别人独特的见解;我都会一一做好笔记,以便进步; 正文:复杂度分析  一、什么是复杂度分析? 1.数据结构和算法解决是“如何让计算机更快时间、更省空间的解决问题”,而时间、空间复杂度做为数据结构和算法的精髓,很直观说明了代码”多快“”多省“。

 

前言:

  大家都知道数据结构和英语,就如同程序员的两条腿一样;只有不断的积累,学习,拥有了健壮的“双腿”才能越走越远;在数据结构和算法的领域,不得不承认自己就是一只菜鸟;需要不断的学习;在学习过程中,经常会有一些自己的看法,和别人独特的见解;我都会一一做好笔记,以便进步;

正文:复杂度分析

 一、什么是复杂度分析?

1.数据结构和算法解决是“如何让计算机更快时间、更省空间的解决问题”,而时间、空间复杂度做为数据结构和算法的精髓,很直观说明了代码”多快“”多省“。

2.我们可以从执行时间和占用空间来评估数据结构和算法的性能,也就空间复杂度、时间复杂度,统称为复杂度。

3.复杂度描述的是算法执行时间(或占用空间)与数据规模的增长关系。

二、为什么要进行复杂度分析?

1.测试环境的不稳定因素(如同样的代码,i7比i3快得多),测试规模对测试结果影响很大(有些算法更适用于大规模数据),复杂度分析有不依赖执行环境、成本低、效率高、易操作、指导性强的特点。

2.掌握复杂度分析,将能编写出性能更优的代码,有利于降低系统开发和维护成本。

三、如何进行复杂度分析?

1.大O表示法

1)所有代码的执行时间 T(n) 与每行代码的执行次数 n 成正比

  T(n) = O(f(n))

其中T(n)表示算法执行总时间,f(n)表示每行代码执行总次数,而n往往表示数据的规模。

大 O 时间复杂度并不具体表示代码真正的执行时间,而是表示代码执行时间随数据规模增长的变化趋势,也叫作渐进时间复杂度,简称时间复杂度,

常量阶、低阶以及系数实际上对这种增长趋势不产决定性影响,所以在做时间复杂度分析时忽略这些项。

2.复杂度分析法则

1)单段代码看高频:比如循环。

2)多段代码取最大:比如一段代码中有单循环和多重循环,那么取多重循环的复杂度。

3)嵌套代码求乘积:比如递归、多重循环等

4)多个规模求加法:比如方法有两个参数控制两个循环的次数,那么这时就取二者复杂度相加。

四、常用的复杂度级别?

多项式阶:随着数据规模的增长,算法的执行时间和空间占用,按照多项式的比例增长。包括, O(1)(常数阶)、O(logn)(对数阶)、O(n)(线性阶)、O(nlogn)(线性对数阶)、O(n^2)(平方阶)、O(n^3)(立方阶)

非多项式阶:随着数据规模的增长,算法的执行时间和空间占用暴增,这类算法性能极差。包括, O(2^n)(指数阶)、O(n!)(阶乘阶)

五、如何掌握好复杂度分析方法?

复杂度分析关键在于多练,所谓孰能生巧。

六、最好、最坏、平均、均摊时间复杂度

一、概念:

1.最坏情况时间复杂度:代码在最理想情况下执行的时间复杂度。
2.最好情况时间复杂度:代码在最坏情况下执行的时间复杂度。
3.平均时间复杂度:用代码在所有情况下执行的次数的加权平均值表示。
4.均摊时间复杂度:在代码执行的所有复杂度情况中绝大部分是低级别的复杂度,个别情况是高级别复杂度且发生具有时序关系时,可以将个别高级别复杂度均摊到低级别复杂度上。基本上均摊结果就等于低级别复杂度。

二、为什么要引入这4个概念?

1.同一段代码在不同情况下时间复杂度会出现量级差异,为了更全面,更准确的描述代码的时间复杂度,所以引入这4个概念。
2.代码复杂度在不同情况下出现量级差别时才需要区别这四种复杂度。大多数情况下,是不需要区别分析它们的。

三、如何分析平均、均摊时间复杂度?

1.平均时间复杂度
代码在不同情况下复杂度出现量级差别,则用代码所有可能情况下执行次数的加权平均值表示。
2.均摊时间复杂度
两个条件满足时使用:1)代码在绝大多数情况下是低级别复杂度,只有极少数情况是高级别复杂度;2)低级别和高级别复杂度出现具有时序规律。均摊结果一般都等于低级别复杂度。

 有人说,我们项目之前都会进行性能测试,再做代码的时间复杂度、空间复杂度分析,是不是多此一举呢?

每段代码都分析一下时间复杂度、空间复杂度,是不是很浪费时间呢?

我不认为是多此一举,渐进时间,空间复杂度分析为我们提供了一个很好的理论分析的方向,并且它是宿主平台无关的,能够让我们对我们的程序或算法有一个大致的认识,让我们知道,比如在最坏的情况下程序的执行效率如何,同时也为我们交流提供了一个不错的桥梁,我们可以说,算法1的时间复杂度是O(n),算法2的时间复杂度是O(logN),这样我们立刻就对不同的算法有了一个“效率”上的感性认识。

当然,渐进式时间,空间复杂度分析只是一个理论模型,只能提供给粗略的估计分析,我们不能直接断定就觉得O(logN)的算法一定优于O(n), 针对不同的宿主环境,不同的数据集,不同的数据量的大小,在实际应用上面可能真正的性能会不同,个人觉得,针对不同的实际情况,进而进行一定的性能基准测试是很有必要的,比如在统一一批手机上(同样的硬件,系统等等)进行横向基准测试,进而选择适合特定应用场景下的最有算法。

综上所述,渐进式时间,空间复杂度分析与性能基准测试并不冲突,而是相辅相成的,但是一个低阶的时间复杂度程序有极大的可能性会优于一个高阶的时间复杂度程序,所以在实际编程中,时刻关心理论时间,空间度模型是有助于产出效率高的程序的,同时,因为渐进式时间,空间复杂度分析只是提供一个粗略的分析模型,因此也不会浪费太多时间,重点在于在编程时,要具有这种复杂度分析的思维。

小舟从此逝,江海寄余生。 --狐狸
目录
相关文章
|
22天前
|
机器学习/深度学习 算法 搜索推荐
从理论到实践,Python算法复杂度分析一站式教程,助你轻松驾驭大数据挑战!
【10月更文挑战第4天】在大数据时代,算法效率至关重要。本文从理论入手,介绍时间复杂度和空间复杂度两个核心概念,并通过冒泡排序和快速排序的Python实现详细分析其复杂度。冒泡排序的时间复杂度为O(n^2),空间复杂度为O(1);快速排序平均时间复杂度为O(n log n),空间复杂度为O(log n)。文章还介绍了算法选择、分而治之及空间换时间等优化策略,帮助你在大数据挑战中游刃有余。
46 4
|
5天前
|
并行计算 算法 IDE
【灵码助力Cuda算法分析】分析共享内存的矩阵乘法优化
本文介绍了如何利用通义灵码在Visual Studio 2022中对基于CUDA的共享内存矩阵乘法优化代码进行深入分析。文章从整体程序结构入手,逐步深入到线程调度、矩阵分块、循环展开等关键细节,最后通过带入具体值的方式进一步解析复杂循环逻辑,展示了通义灵码在辅助理解和优化CUDA编程中的强大功能。
|
12天前
|
算法
PID算法原理分析
【10月更文挑战第12天】PID控制方法从提出至今已有百余年历史,其由于结构简单、易于实现、鲁棒性好、可靠性高等特点,在机电、冶金、机械、化工等行业中应用广泛。
20 0
|
14天前
|
移动开发 算法 前端开发
前端常用算法全解:特征梳理、复杂度比较、分类解读与示例展示
前端常用算法全解:特征梳理、复杂度比较、分类解读与示例展示
15 0
|
2月前
|
存储 JSON NoSQL
redis基本数据结构(String,Hash,Set,List,SortedSet)【学习笔记】
这篇文章是关于Redis基本数据结构的学习笔记,包括了String、Hash、Set、List和SortedSet的介绍和常用命令。文章解释了每种数据结构的特点和使用场景,并通过命令示例演示了如何在Redis中操作这些数据结构。此外,还提供了一些练习示例,帮助读者更好地理解和应用这些数据结构。
redis基本数据结构(String,Hash,Set,List,SortedSet)【学习笔记】
|
18天前
|
算法
PID算法原理分析及优化
【10月更文挑战第6天】PID控制方法从提出至今已有百余年历史,其由于结构简单、易于实现、鲁棒性好、可靠性高等特点,在机电、冶金、机械、化工等行业中应用广泛。
23 0
|
2月前
|
算法 搜索推荐 开发者
别再让复杂度拖你后腿!Python 算法设计与分析实战,教你如何精准评估与优化!
在 Python 编程中,算法的性能至关重要。本文将带您深入了解算法复杂度的概念,包括时间复杂度和空间复杂度。通过具体的例子,如冒泡排序算法 (`O(n^2)` 时间复杂度,`O(1)` 空间复杂度),我们将展示如何评估算法的性能。同时,我们还会介绍如何优化算法,例如使用 Python 的内置函数 `max` 来提高查找最大值的效率,或利用哈希表将查找时间从 `O(n)` 降至 `O(1)`。此外,还将介绍使用 `timeit` 模块等工具来评估算法性能的方法。通过不断实践,您将能更高效地优化 Python 程序。
49 4
|
2月前
|
算法 程序员 Python
程序员必看!Python复杂度分析全攻略,让你的算法设计既快又省内存!
在编程领域,Python以简洁的语法和强大的库支持成为众多程序员的首选语言。然而,性能优化仍是挑战。本文将带你深入了解Python算法的复杂度分析,从时间与空间复杂度入手,分享四大最佳实践:选择合适算法、优化实现、利用Python特性减少空间消耗及定期评估调整,助你写出高效且节省内存的代码,轻松应对各种编程挑战。
31 1
|
19天前
|
算法
数据结构(复杂度)
数据结构(复杂度)
14 0
|
20天前
|
存储 机器学习/深度学习 算法
探索数据结构:入门及复杂度的解锁
探索数据结构:入门及复杂度的解锁