Skip to content

Commit 72f39f4

Browse files
BolexLiuBolexLiu
committed
老夫反手就是一张过去的CD，听听那是算法时间复杂度和大O表示法
1 parent 6df4ab4 commit 72f39f4

2 files changed

Lines changed: 177 additions & 1 deletion

File tree

‎README.md‎

Lines changed: 2 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -8,7 +8,8 @@
88
- 110801914
99

1010
## android
11-
- [android开发中相见恨晚的冷知识【简单说】](http://www.jianshu.com/p/6450b0da5876)
11+
- [老夫反手就是一张过去的CD，听听那是算法时间复杂度和大O表示法]( http://www.jianshu.com/p/ee9400b8c50f)
12+
- [android开发中相见恨晚的冷知识【简单说】](http://www.jianshu.com/p/6450b0da5876)
1213
- [英语不好？是时候打造一款AndroidStudio中记单词的翻译插件了](http://www.jianshu.com/p/760c98f682ea)
1314
- [少年，老夫带你撸一把Android项目框架，你可想学？](http://www.jianshu.com/p/06d417b554ef)
1415
- [Android ADB命令?这一次我们不再死记!【简单说】](http://www.jianshu.com/p/56fd03f1aaae)

‎android/老夫反手就是一张过去的CD，听听那是算法时间复杂度和大O表示法.md‎

Lines changed: 175 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,175 @@
1+
现在是伟大美好的端午佳节时间，你现在是在回家的路上吗？祝各位简友们~~生日快乐~~！！！啪啪啪！ 又调皮，明明是中秋节快乐好咩~。
2+
![](http://upload-images.jianshu.io/upload_images/1110736-df9fa75d99a42be9.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/1240)
3+
4+
今日有酒尽早醉，明日无酒老夫我开盖再来一瓶。 咱今天扒一下软件编程中的算法时间复杂度。
5+
6+
“玛德，智 ........勇双全。一说算法之类的东西晚生我就想打哈欠，犯困。(o-ωｑ)).oO ”
7+
8+
![](http://upload-images.jianshu.io/upload_images/1110736-529bd1c0d4df9bb0.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/200)
9+
10+
“是不是感觉老有知识咳不出来，又咽不下去？老夫反手就是一张过去的CD，听听那是我们的XX”
11+
12+
![](http://upload-images.jianshu.io/upload_images/1110736-d746da2665e46654.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/200)
13+
14+
“巴拉拉能量，麻辣割鸡小魔仙全身变。kuang！别担心，大鸡排今天讲的足够简单、 粗暴~~不戴X~~，易理解。” 快坐上来吧，搞起。搞起。
15+
16+
-----
17+
18+
# 目录
19+
- 前言
20+
- 概念
21+
- 例子
22+
- 题外话
23+
24+
----
25+
26+
## 前言
27+
到今天为止，可能我们的确不会自己再去经常编写一个高效的算法。因为在各大框架或语言原生的API里，它们已经帮业务开发的程序员将最优的算法都实现了。所以我们很少用到在实际场景中，特别是作为大前端开发人员更加很少接触到。但是无论从计算机编程基础、以及编写更优秀的性能代码，这块的知识是任然是非常重要的。
28+
29+
### 基础与流行
30+
人的一生是有限的，个人认为在编程技术栈中的学习即是一种投资行为。做我们这行的行业积累是会过期的。所以我将技术知识粗略的划分为两块。
31+
即：**基础编程知识流、流行编程知识流。**
32+
基础知识是牢固而不容易过期的，而流行编程知识往往是偏向前沿技术而活泼不稳定的，把时间轴拉长来看，新技术是不断的被迭代的。
33+
34+
也就是说如果我们把 sql、算法、编程思想 ...归结为基础编程知识来看。java语言、kotlin语言、android、React ...这种知识是当前流行编程知识流。
35+
36+
那么流行知识是一个反复学习新技术，不断的扔掉成旧知识的一个过程。而恰恰相反，基础知识是不会和新技术产生冲突交集的。所以如果你是一个刚刚入行不久的攻城狮，那么从投资的角度来看，我建议对基础编程知识的前期投资是越丰厚越好，而且是稳赚不陪的卖买。
37+
正式开发环境中很多时候是飞机大炮造到一半，发现零件的质量不够好。框架子搞了一堆再牛逼，却写不出好东西或则说无法发挥最大的性能。
38+
39+
### 用优质的代码解决硬件成本
40+
简单来说，就是如果你代码的执行算法太慢，将导致需要用硬件来撑起运行速度。这就是在过多的消耗硬件成本。而作为行业内人员或者boss，你是愿意将刀刃(钱)用在优秀的工程师上，还是高昂价格的机器上。相信这个问题，我只需要提出,你就已经有了结论。我不作过多的阐述。
41+
42+
---
43+
44+
## 概念
45+
46+
我们今天只弄明白两点，到底什么是算法时间复杂度？什么是大O表示法？
47+
48+
### 算法时间复杂度
49+
好，怎么理解？一句话来说就是
50+
**你用代码做某一件事件，所消耗的总体时间长度,就是该事件(算法)的时间复杂度。**
51+
这里暂且不说平均复杂度和实际复杂度。我们后面再讲这些。
52+
53+
### 大O表示法
54+
大O表示法呢？
55+
**一个用来表示算法时间复杂度的公式名称，用于指出该算法的效率有多快。在计算机领域我们用函数来表示**
56+
当我第一次接触到`大O表示法`时，我还在纠结，那`小o表示法`又是什么。其实根本没有这种东西。`大O表示法`仅仅是一个名称。
57+
58+
```
59+
//表达式其中n表示要执行的次数。
60+
O(n)
61+
```
62+
---
63+
64+
## 例子
65+
- O(n) 傻找算法(线性时间)
66+
- O(log n) 二分查找
67+
68+
黑魔法大鸡排把你的老婆抓起来藏在召唤师峡谷的地窖中。依照你过人的聪明智慧，你用敏锐的嗅觉一路上根据老婆的味道，靠鼻子闻到了地窖。打开一看。**里面有1000个和你老婆一模一样的蜡像，但其中有一个是真正的老婆。**放眼望去，你并不知道哪个是你的老婆，因为他们实在太像了。由于被大鸡排下了诅咒，真正的老婆被封印了起来，只有通过真爱么么哒才能唤醒 （づ￣3￣）づ╭❤～。
69+
70+
### O(n) 傻找算法(线性时间)
71+
72+
此刻你急中生智，骂道：“什么烂剧情例子,用鼻子闻到老婆的味道跟我聪明的智慧有个毛关系啊？,还tm要一个么么哒”，你只好决定**一个一个亲下去。从第一个亲到最后一个**。
73+
我们用代码来表示这个过程就是：
74+
```
75+
//999个假老婆+一个真的
76+
List<Wife> Wifes= {蜡像，蜡像，蜡像...真老婆，蜡像}；
77+
// 我自己
78+
Lead myself =new Lead()；
79+
80+
for(i=0; i<=Wifes.length; ++i){
81+
boolean resurrection =kiss(Wifes.get(i))； //么么哒唤醒
82+
if(resurrection ){
83+
Log.i(“已找到老婆他在”+i+“个,赶紧抬回家，远离召唤师峡谷”)；
84+
return ;
85+
}
86+
}
87+
88+
boolean kiss(Wife mWife){
89+
//调用自己的么么哒方法 返回真假
90+
return myself.kiss(mWife)；
91+
}
92+
```
93+
这个过程是我们有一个Wifes容器装下了999个蜡像和一个真正的老婆。然后myself 是自己,拥有一个kiss方法用来唤醒老婆并返回真假。这里模拟从第一个开始kiss到最后一个。当我们找到了老婆就停止一切行为。
94+
95+
那么我们的时间复杂度是：最多尝试**1000**次，即** O(n)**来表示，其中**n**表示次数。是不是很简单。
96+
97+
这是最糟糕的结果，大鸡排将你的wife放在最后一个位置，你从第一个开始亲，亲到最后一个。你需要尝试**1000**次。但绝不会超过这个范围。当然实际情况也可能是**O(1)**，第一次成功了。
98+
99+
我们通过这个算法得到了时间复杂度公式： **O(n)**
100+
101+
### O(log n) 二分查找
102+
接着上面的列子。还记得召唤师峡谷里有个商店老爷爷吗？他说能为你打开此次寻找的天机。将所有蜡像的序号都展示出来，并且他每次都能告诉你整个区间内是否存在真正的老婆。你想了想那么我可以从中间对折拆分找呀，这样可以每次直接排除掉一半。这个过程就像：
103+
104+
第一次询问:** 500~1000** 他说不存在， **1~499**那么一定存在。
105+
第二次询问:** 250~499** 他说不存在， **1~249**那么一定存在。
106+
第三次询问:** 125~249** 他说不存在， **1~124**那么一定存在。
107+
第四次询问:** 63~124** 他说不存在， **1~62**那么一定存在。
108+
第五次询问:** 31~62** 他说不存在， **1~30**那么一定存在。
109+
第六次询问:** 15~30** 他说不存在， **1~15**那么一定存在。
110+
第七次询问:** 7~14** 他说不存在， **1~6**那么一定存在。
111+
第八次询问:** 3~6** 他说不存在， **1~2**那么一定存在。
112+
第九次询问:** 2** 他说不对，那么结果只剩下**1**了。
113+
114+
好，我们捋一捋。实际每次询问我们都可以排除一半绝对不可能存在的。也就是说最多我们需要经过**9步**即可完成从**1000个**老婆中出真正的老婆。
115+
如果我们把它写成代码就会是这个样子：
116+
```
117+
//999个假老婆+一个真的
118+
List<Wife> Wifes= {蜡像，蜡像，蜡像...真老婆，蜡像}；
119+
// 我自己
120+
Lead myself =new Lead()；
121+
122+
int low=0; //最低位
123+
int high = Wifes.length-1; //最高位
124+
int mid; //折中猜想数
125+
126+
while( low<=high){
127+
mid=(low+higt)/2
128+
likeWife=Wifes.get(mid)；
129+
if( kiss(likeWife)){
130+
Log.i(“已找到老婆他在”+mid+“个,赶紧抬回家，远离召唤师峡谷”)；
131+
return ;
132+
}
133+
boolean deviation= elderlyHelp(likeWife)；
134+
if(deviation){ //往左偏移 表示大了
135+
high=mid-1；
136+
}esle{ //往右偏移 表示小了
137+
low=mid+1；
138+
}
139+
}
140+
141+
}
142+
143+
//老爷爷的帮助 返回区间内是否包含
144+
boolean elderlyHelp(){
145+
····
146+
}
147+
148+
boolean kiss(Wife mWife){
149+
//调用自己的么么哒方法 返回真假
150+
return myself.kiss(mWife)；
151+
}
152+
```
153+
这样我们就推倒出二分法查找实际是是对数函数的反向幂运算。所以推倒出公式为：**O(log n)**
154+
155+
稍微说一下log对数运算，也许你学过又忘了。log以10为底数多少次幂结果等于100，其实就是指多少个10相乘的结果为100。答案是两个：10 × 10 = 100。所以log以10为底数的 2次幂等于100。
156+
157+
### O(n)对比 O(log n)
158+
159+
假定我们每一次myself.kiss用于激活的方法需要1秒钟执行。当采用第一种算法时，时间复杂度为O(n) ，那么需要**1000秒**才能找出老婆。但如果采用了二分查找，时间复杂度为 O(log n) ，那么仅需要**9秒**即可完成操作。其中n表示次数。那么由此可见O(log n) 比O(n)要快。当元素越多的时候，执行的效率就尤其具有可比性。
160+
161+
---
162+
### 题外话
163+
164+
好，那么到这里就讲完了今天的内容啦。如果你感兴趣的话可以再去了解**O(n!)** n阶乘的时间复杂度。当n阶越高，消耗的时间越长。这是计算机领域非常经典的旅行商问题。 感兴趣戳[这里](http://baike.baidu.com/item/%E6%97%85%E8%A1%8C%E5%95%86%E9%97%AE%E9%A2%98)过去继续深入阅读。
165+
166+
>**旅行推销员问题**（英语：**Travelling salesman problem**, **TSP**）是这样一个问题：给定一系列城市和每对城市之间的距离，求解访问每一座城市一次并回到起始城市的最短回路。它是[组合优化](http://baike.baidu.com/item/%E7%BB%84%E5%90%88%E4%BC%98%E5%8C%96)中的一个[NP](http://baike.baidu.com/item/NP/7470332)困难问题，在[运筹学](http://baike.baidu.com/item/%E8%BF%90%E7%AD%B9%E5%AD%A6/1559)和[理论计算机科学](http://baike.baidu.com/item/%E7%90%86%E8%AE%BA%E8%AE%A1%E7%AE%97%E6%9C%BA%E7%A7%91%E5%AD%A6)中非常重要。
167+
168+
169+
看完本篇并不能让你成一个优秀的工程狮，这是入门级别的基础知识。但如果因为是你看完这篇文章后产生了这种想法，我的目的就达到了，至少已经在通往优秀工程狮的路上了。那么更多的知识还需要长久的打磨和学习。共勉 加油！
170+
171+
---
172+
# 如何下次找到我?
173+
- 关注我的简书
174+
- 本篇同步Github仓库:[https://github.com/BolexLiu/MyNote](https://github.com/BolexLiu/MyNote)  (可以关注)
175+
![](http://upload-images.jianshu.io/upload_images/1110736-f0a700624e0723ae.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/1240)

0 commit comments

Comments
 (0)