每个人都有自己的知识体系。
Toggle navigation
Home
随笔
C#/.Net
树莓派 / Raspberry
皓月汉化组
Beego
Golang
OxideMod
apache
haproxy
windows
Java
Objective-C
日语/罗马音歌词/日语常识
MongoDB
python
电学
公告
Minecraft服务器-公告
NanoPi
C4D （CINEMA 4D）
生活
推流/m3u8/rtmp/rtsp
Unity3d
ffmpeg
数据结构
区块链
tarui
UnityForPSVita
About Me
Archives
Tags
数据结构和算法笔记 - 4 时间复杂度和空间复杂度II
2024-03-26 17:25:28
18
0
0
akiragatsu
在算法分析时、 语句总执行次数T(n)是关于问题规模n的函数、 进而分析T(n)随着n的变化情况并确定T(n)的数量级 算法的时间复杂度、也就是算法的时间量度 记做 T(n)=O(f(n)) 他表示随着规模n的增大、算法执行时间的增长率和f（n）的增长率想用、曾作算法的渐进时间复杂度。其中f(n)是问题规模n的某个函数。 用大写O()来体现算法时间复杂度的记法、可叫做大O记法 一般情况下 随着输入规模n增加 T(n)增长最慢的算法 最为优先 —————————— 推导大O阶方法 - 用常数1取代运行时间中的又有加法常数 - 在修改后的运行次数函数中、只保留最高项 - 如果最高阶创业板在且不是1、则去除与这个项相乘的常数 - 得到最后的结果就是大O阶、也就是时间复杂度 ##线性阶 一般含有非嵌套循环涉及线性阶、线性阶就是随着问题规模n的扩大而扩大 O（n） ##平方阶 含有嵌套循环的程序 比如 n次循环嵌套一个循环n次的循环 时间复杂度为O(n^2) 循环的时间复杂度 = 循环体的复杂度乘以该循环的运行次数 ##对数阶 int i=1,n=100; while(i < n) { i = i * 2; } 其实i就是2的指数、多少次方的结果能够不比n小 就循环完毕 求多少次方 就是对数 所以循环次数 为 log(2)n 所以时间复杂度为O(logn)
Pre:
数据结构和算法笔记 - 6 线性表I
Next:
数据结构和算法笔记 - 3 时间复杂度和空间复杂度
0
likes
18
Weibo
Wechat
Tencent Weibo
QQ Zone
RenRen
Submit
Sign in
to leave a comment.
No Leanote account?
Sign up now.
0
comments
More...
Table of content
akiragatsu
No Leanote account? Sign up now.