算法学习 | 大O表示法

简介: 上一节我们使用了两种不同的方式来获得两个数的最大公约数,那么如何判断我们应该使用哪一种方式呢?这里就涉及到了算法的时间复杂度、空间复杂度、稳定性等几个方面的因素,这次我们要讨论的大O表示法就是用来表示时间复杂度。

上一节我们使用了两种不同的方式来获得两个数的最大公约数,那么如何判断我们应该使用哪一种方式呢?这里就涉及到了算法的时间复杂度、空间复杂度、稳定性等几个方面的因素,这次我们要讨论的大O表示法就是用来表示时间复杂度。
image

大O表示法法让你能够比较操作数,它指出了算法运行时间的增速——《算法图解》

开始前的准备

在开始学习之前请先确认一下你是否还记得高中所学的对数。

log39

如果你可以一眼看出这个对数的结果是3,那么我们就可以进入接下来的部分了。

什么是大O表示法

大O表示法是一种特殊的表示法,指出了算法的运算速度有多快。

首先我们来看一个函数,当我们输入n时,函数的结果是1+2+...+n的和。

int add(int n){
    int a=0;              //第1行
    int i;                //第2行
    for(i=1;i<=n;i++){    //第3行
        a+=i;             //第4行
    }
    return a;             //第5行
}
AI 代码解读

在这里for语句需要执行n次,我们就称他是时间复杂度为O(n)。

之所把他叫做大O表示法,仅仅因为操作数前面有一个大O。

这里我们可以再看一个二分查找的例子,二分查找类似于我们小时候玩的猜数游戏,当你猜一个数时,你的小伙伴会告诉你这个数是否正确,偏大了还是偏小了。直到你最终猜出正确的答案。比如我们猜1-100中的一个数,我们会猜50,得到结果之后就可以把范围缩小到1-50或者51-100,以此类推。每次我们都能将查找的范围缩小一半。

所以我们每次的查找范围就是n,n/2,n/4,....直到

n/2k

其中k就是循环的次数,随着k的增大,他们的比值将越来越接近于1。

n/2k=1

可得

k=log2N

即当我们需要在长度为N的表上查找的时候,最多需要查找的次数是

log2N

所以二分查找的时间复杂度即为

O(log2N)

注意事项:算法的速度并非指时间,而是操作数的增速。

常见的大o运行时间

1.

O(logxN)

这样的算法包括二分查找

2.

O(N)

这样的算法包括简单查找
3.

O(NlogxN)

这样的算法包括快速排序
4.

O(N)2

这样的算法包括选择排序

参考资料

1.《算法图解》

2.《算法(第四版)》

目录
打赏
0
0
0
0
5
分享
相关文章
为什么要学习数据结构与算法
今天,我向大家介绍一门非常重要的课程——《数据结构与算法》。这门课不仅是计算机学科的核心,更是每一位开发者从“小白”迈向“高手”的必经之路。
为什么要学习数据结构与算法
架构学习:7种负载均衡算法策略
四层负载均衡包括数据链路层、网络层和应用层负载均衡。数据链路层通过修改MAC地址转发帧;网络层通过改变IP地址实现数据包转发;应用层有多种策略,如轮循、权重轮循、随机、权重随机、一致性哈希、响应速度和最少连接数均衡,确保请求合理分配到服务器,提升性能与稳定性。
1090 11
架构学习:7种负载均衡算法策略
【EMNLP2024】基于多轮课程学习的大语言模型蒸馏算法 TAPIR
阿里云人工智能平台 PAI 与复旦大学王鹏教授团队合作,在自然语言处理顶级会议 EMNLP 2024 上发表论文《Distilling Instruction-following Abilities of Large Language Models with Task-aware Curriculum Planning》。
2024重生之回溯数据结构与算法系列学习之串(12)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丟脸好嘛?】
数据结构与算法系列学习之串的定义和基本操作、串的储存结构、基本操作的实现、朴素模式匹配算法、KMP算法等代码举例及图解说明;【含常见的报错问题及其对应的解决方法】你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
2024重生之回溯数据结构与算法系列学习之串(12)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丟脸好嘛?】
2024重生之回溯数据结构与算法系列学习之栈和队列精题汇总(10)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构王道第3章之IKUN和I原达人之数据结构与算法系列学习栈与队列精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
2024重生之回溯数据结构与算法系列学习之单双链表精题详解(9)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构王道第2.3章之IKUN和I原达人之数据结构与算法系列学习x单双链表精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
2024重生之回溯数据结构与算法系列学习(8)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构王道第2.3章之IKUN和I原达人之数据结构与算法系列学习x单双链表精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
2024重生之回溯数据结构与算法系列学习之王道第2.3章节之线性表精题汇总二(5)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
IKU达人之数据结构与算法系列学习×单双链表精题详解、数据结构、C++、排序算法、java 、动态规划 你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
2024重生之回溯数据结构与算法系列学习之单双链表【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构之单双链表按位、值查找;[前后]插入;删除指定节点;求表长、静态链表等代码及具体思路详解步骤;举例说明、注意点及常见报错问题所对应的解决方法

热门文章

最新文章

AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等