论坛 › 《数据结构和算法》（应用版，Python） › 第002讲：你怎么知道你的程序跑得比别人快 | 课后作业及参考答案

小甲鱼 发表于 2023-8-7 01:47:41

第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
3. 课程的最后演示了旅行商问题，解决该问题通常算法的时间复杂度是O(n!)，那么对于 5 个城市而言，最多需要尝试多少次才能得出答案呢？~F)zCA'N:
8fDF!Od3gv.=)s6m-%hwr
1]U2baR`w)'Auzey!CK}
4. 请分析下面这段代码，猜一猜它的时间复杂度分别是多少？eOl*Zd(
yh,#Pu:;=<8s~3bgM'|
def linear_search(arr, target):
    for i in range(len(arr)):
      if arr == target:
            return i
    return -1
3S;6wk<s5>z=4I8|F(&Z$uT?t*2KRP
5. 请分析下面这段代码，猜一猜它的时间复杂度分别是多少？^'UznVgkSK
`AH|."ywD8LQPB%qvFkGWMxb~
def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    while left <= right:
      mid = (left + right) // 2
      if arr == target:
            return mid
      elif arr < target:
            left = mid + 1
      else:
            right = mid - 1
    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
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=+*
这样可以有效地减少不必要的计算和数据处理，从而优化性能。96+L"3{]P0
3vZ@NB"kAD}S1?[+mzF*:g^4I!W_
对于某些问题，该算法可以将将原先 O(n2) 或 O(n3) 降低到 O(n) 的时间复杂度。|c83^-'2
mGu+zjC#%I7X'S!{L29i P
还是蛮有料的~版权属于：https://fishc.com.cn
&E,Ku"Re.M{cGj3ZtL`hai+
{:10_248:} 版权属于：https://fishc.com.cn
&u<$kzYP`L}5oiDnS+X(U9
?H[>PMb2xQ;nKJWwql-i1_
原理Powered by https://fishc.com.cn
<y'aRLM4,)6ik=|tP5wUI
滑动窗口算法的基本思想是使用一个窗口在数据（如数组或列表）上滑动，并在滑动过程中保持和更新一些有用的状态信息。|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
https://fishc.oss-cn-hangzhou.aliyuncs.com/Videos/Algorithm/SlideWindow.mp4hc]=Qr(*KF
9
（请仔细查看动画演示，这个过程非常重要）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
2 4 0 9 4 0 4 3 1 2
0 0 6 3 3 3 3 6 4 6
5 2 8 5 4 5 8 0 7 8
5 6 9 2 4 8 9 7 1 3
4 9 5 1 1 6 2 0 1 9
8 3 3 3 0 2 5 8 3 7
7 1 3 3 6 7 9 6 2 1
8 5 8 4 0 9 2 5 0 0
5 9 1 5 2 7 9 8 5 9
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
73167176531330624919225119674426574742355349194934
96983520312774506326239578318016984801869478851843
85861560789112949495459501737958331952853208805511
12540698747158523863050715693290963295227443043557
66896648950445244523161731856403098711121722383113
62229893423380308135336276614282806444486645238749
30358907296290491560440772390713810515859307960866
70172427121883998797908792274921901699720888093776
65727333001053367881220235421809751254540594752243
52584907711670556013604839586446706324415722155397
53697817977846174064955149290862569321978468622482
83972241375657056057490261407972968652414535100474
82166370484403199890008895243450658541227588666881
16427171479924442928230863465674813919123162824586
17866458359124566529476545682848912883142607690042
24219022671055626321111109370544217506941658960408
07198403850962455444362981230987879927244284909188
84580156166097919133875499200524063689912560717606
05886116467109405077541002256983155200055935729725
71636269561882670428252483600823257530420752963450
并且，我们将 “求和” 变成 “求积”。T<76Ga
Wx_4?Fpt){*k2$A@R6E~m+c!
请使用代码找出相邻 13 个数字的最大乘积。6X2)<u:DP
f{WQgyoT]pbA~
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
**** Hidden Message *****Powered by https://fishc.com.cn
`G4&#O0.@Bc%=9!E>3iA
动动手答案：来自：https://fishc.com.cn
~2."C4Nd@s-Hjk&$mvLUI*a =?JxK3
**** Hidden Message *****来自：https://fishc.com.cn
7TeStRic}G!9Fv^`6VzrXE%g{1K-I

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