第002讲：你怎么知道你的程序跑得比别人快 | 课后作业及参考答案

小甲鱼

第002讲：你怎么知道你的程序跑得比别人快

E#zh7ps
13a(uNt$W@q6'Q9B"UCs57A
问答题：4vLx.w+lu(
=Zx-O(TeFs`5~CqPSr@YM2_ m
0. 如果猜数字游戏的规模是 1 万、10 万和 100 万，那么使用二分查找算法，分别最多需要尝试多少次呢？e9=PL
&@t|XolB,!8f05U>NO2W^
Id)|Spim5l{*KVT0#^"]~XQkH;g43
1. 程序员通过时间复杂度来估算程序的平均工作时间，对吗？xTQ2M.
x0*dL,-l=eW9%gaZ~XftSz@BU}2:5F
6M@`IbEJ[ sX&8>Le{4W*xoO$^;
2. 效率最高的时间复杂度是多少？来自：https://fishc.com.cn
(s}rYD*c;PA|@.<T8flv^F
2M[ts*9S7`C";_xUgG4qha
3. 课程的最后演示了旅行商问题，解决该问题通常算法的时间复杂度是O(n!)，那么对于 5 个城市而言，最多需要尝试多少次才能得出答案呢？~F)zCA'N:
8fDF!Od3gv.=)s6m-%hwr
1]U2baR`w)'Auzey!CK}
4. 请分析下面这段代码，猜一猜它的时间复杂度分别是多少？eOl*Zd(
yh,#Pu:;=<8s~3bgM'|[Gf&B$

1. def linear_search(arr, target):
   
2.     for i in range(len(arr)):
   
3.         if arr[i] == target:
   
4.             return i
   
5.     return -1

复制代码

3S;6wk<s5>z=4I8|F(&Z$uT?t*2KRP
5. 请分析下面这段代码，猜一猜它的时间复杂度分别是多少？^'UznVgkSK
`AH|."ywD8LQPB%qvFkGWMxb~

1. def binary_search(arr, target):
   
2.     left, right = 0, len(arr) - 1
   
3.     while left <= right:
   
4.         mid = (left + right) // 2
   
5.         if arr[mid] == target:
   
6.             return mid
   
7.         elif arr[mid] < target:
   
8.             left = mid + 1
   
9.         else:
   
10.             right = mid - 1
    
11.     return -1

复制代码

n`2Yq?B(Pjw')Gm=3iW,J%b
动动手：0O.Azx:_+,
C?dkn:#m_VBeR8(aujDoQ!z0pU5
动动手这个环节设立在零基础系列课程中，主要目的是提高大家的动手能力并培养编程思维。2t){}%]@gi
80CQ34x<'NJ+=?hjTg[.Ena
但在数据结构和算法中，我们给大家增加一个新的 “功能”，在设立挑战的同时，试图让大家学到一些课堂上没有的东西。T&MW-]E
0F=P&;4:G9#2(A$p*qy r-fTb<s
下面，就让我们先来快速学习一下滑动窗口算法吧~iND!Ay35B
[v|]OVT}3N,&DU+ds19lW
介绍来自：https://fishc.com.cn
+Sb[$VAh2`5efC|4m)*Uq=7TXO
滑动窗口算法（Sliding Window Algorithm）是一种常用的优化算法，主要用于解决一些数组、列表或字符串等线性结构上的问题。t^;2k9r
:wR@IJa$n7BU&o!1LqHXm+4e~tN*
该算法的主要思想是维护一个动态的窗口，窗口在数据结构上前进（或滑动）并根据需要改变其大小。pzlLW8
LF$@NV=+*[EzR;-TC}PYJoAs
这样可以有效地减少不必要的计算和数据处理，从而优化性能。96+L"3{]P0
3vZ@NB"kAD}S1?[+mzF*:g^4I!W_
对于某些问题，该算法可以将将原先 O(n²) 或 O(n³) 降低到 O(n) 的时间复杂度。|c83^-'2
mGu+zjC#%I7X'S!{L29i P
还是蛮有料的~版权属于：https://fishc.com.cn
&E,Ku"Re.M{cGj3ZtL`hai+
版权属于：https://fishc.com.cn
&u<$kzYP`L}5oiDnS+X(U9
?H[>PMb2xQ;nKJWwql-i1_
原理Powered by https://fishc.com.cn
<y'aRLM4,)6ik=|tP5wUI[O~H}nz
滑动窗口算法的基本思想是使用一个窗口在数据（如数组或列表）上滑动，并在滑动过程中保持和更新一些有用的状态信息。|g"L>
hH}xGvjp6)P>7*8S-2#ziUru@ZTCq
滑动窗口可以看作是一个队列，可以从一端添加元素，从另一端删除元素。ECadcwyr4
|2hMJ!p'X:LK}8E#,];I"% q1x[
当窗口向右移动时，一些元素会进入窗口，一些元素会离开窗口。RqavBY
S9Lz"N;u~>|xo)s3OgVKR%T_6U]cB
在每一步，我们都可以根据新加入的元素和离开的元素更新我们的状态。@f>%b GWr
_(kto']Ui,p)XVYcx.NwRC?9$B*%
H<F4g3"PR^bN ApT6vB*rDO'x
演示Powered by https://fishc.com.cn
NDA!}2u{<|wbqV=hM 3ReExcsP
比如我们要从 100 个数中找出相邻 3 个数的最大和，那么滑动窗口就非常合适了：5D;p4i
<;fq~zrjoa*@N}_m$Owg]h

如果无法播放，请点击此处在新窗口打开

hc]=Qr(*KF
9[0x-Nu6O'_sV.eKiTHX=,W5q
（请仔细查看动画演示，这个过程非常重要）3|,l5o
[*N9Cm3Kywb%7GWcr6;@I>u~sR}F4
好，那么开始挑战吧~Powered by https://fishc.com.cn
]~$%qH8A>[(mQ73?5pMjRa#
(n8l{u~>QgdG^D,LW)7VS'@E
0. 现在有 100 个数字如下：版权属于：https://fishc.com.cn
t3SkP:#2}$J-O'UT1W@VbCqX&~NfG

1. 2 4 0 9 4 0 4 3 1 2
   
2. 0 0 6 3 3 3 3 6 4 6
   
3. 5 2 8 5 4 5 8 0 7 8
   
4. 5 6 9 2 4 8 9 7 1 3
   
5. 4 9 5 1 1 6 2 0 1 9
   
6. 8 3 3 3 0 2 5 8 3 7
   
7. 7 1 3 3 6 7 9 6 2 1
   
8. 8 5 8 4 0 9 2 5 0 0
   
9. 5 9 1 5 2 7 9 8 5 9
   
10. 6 2 4 1 7 2 9 4 0 0

复制代码

请使用代码找出相邻 3 个数字的最大和。kqXVS}Q[
kt7|X}{:qye$I(8v*H~SNl<su
L~;w!QM2%UTS b'RvX$EK"
1. 现在我们把数字的规模放大 10 倍，变成 1000 个数字：02fdaE!Vp*
5"f.yM10)O:qsw?cxH9$*bL

1. 73167176531330624919225119674426574742355349194934
   
2. 96983520312774506326239578318016984801869478851843
   
3. 85861560789112949495459501737958331952853208805511
   
4. 12540698747158523863050715693290963295227443043557
   
5. 66896648950445244523161731856403098711121722383113
   
6. 62229893423380308135336276614282806444486645238749
   
7. 30358907296290491560440772390713810515859307960866
   
8. 70172427121883998797908792274921901699720888093776
   
9. 65727333001053367881220235421809751254540594752243
   
10. 52584907711670556013604839586446706324415722155397
    
11. 53697817977846174064955149290862569321978468622482
    
12. 83972241375657056057490261407972968652414535100474
    
13. 82166370484403199890008895243450658541227588666881
    
14. 16427171479924442928230863465674813919123162824586
    
15. 17866458359124566529476545682848912883142607690042
    
16. 24219022671055626321111109370544217506941658960408
    
17. 07198403850962455444362981230987879927244284909188
    
18. 84580156166097919133875499200524063689912560717606
    
19. 05886116467109405077541002256983155200055935729725
    
20. 71636269561882670428252483600823257530420752963450

复制代码

并且，我们将 “求和” 变成 “求积”。T<76Ga
Wx_4?Fpt){*k2$A@R6E~m+c!
请使用代码找出相邻 13 个数字的最大乘积。6X2)<u:DP
f{WQgyoT]pbA~[B(e546&$rcPh1!F
Ab a;'j{L_GiEk@xQ=Fr-
2. 上面两道题的答案，时间复杂度分别是多少呢？7,E@g
t.x?$cVLiA;!W"mbz8:I1~g
jc:!6&bF@`#-p|u QP.;ynlzw$
3. 如果求乘积的那道题（第 1 题），你的代码时间复杂度不是 O(n)，那么这道题就是为你准备的：请优化代码，使其时间复杂度变为 O(n)。qXkNb2(AEz
K5Wl1YfcgJi(M>V&Gm',4.#X3U?IuZ
D|LEOC'iV1z74km c,%*fa;R.og+Z=
图一时之快先看答案，你将失去一次锻炼的机会！*moK
zU1"Kyr< {6'H^ME$!#lLq%
请先自己思考和动手，再回复查看参考答案！'ov8!
a=T0&8g:vjsGAVZIY!bp($O_3k
LCYJ$Wba45SX ,!;dI.)Gq(>FgQ
问答题答案：版权属于：https://fishc.com.cn
($VaJH}_,~ePi7-v^@hrb%yS

游客，如果您要查看本帖隐藏内容请回复

Powered by https://fishc.com.cn
`G4&#O0.@Bc%=9!E>3iA[RH"
动动手答案：来自：https://fishc.com.cn
~2."C4Nd@s-Hjk&$mvLUI*a =?JxK3

游客，如果您要查看本帖隐藏内容请回复

来自：https://fishc.com.cn
7TeStRic}G!9Fv^`6VzrXE%g{1K-I