1
銆婅绠楁満绠楁硶璁捐涓庡垎鏋愩�嬭瘯棰?/p>
(B)
杞欢瀛﹂櫌
04
绾?/p>
杞欢宸ョ▼涓撲笟
鍙傝�冪瓟妗?/p>
涓�銆佸～绌洪
锛堝叡
8
灏忛锛?/p>
15
涓┖锛屾瘡绌?/p>
1
鍒嗭紝鍏?/p>
15
鍒嗐�?/p>
锛?/p>
瑙ｏ細
浜屻�佽绠楅锛堝叡
8
灏忛锛屾瘡灏忛
4-12
鍒嗭紝鍏?/p>
53
鍒嗭級
1
锛?/p>
锛?/p>
5
鍒嗭級缁欏嚭鍚堝苟鎺掑簭绠楁硶鏃堕棿澶嶆潅搴?/p>
T(n)
鐨勯�掑綊鏂圭▼銆?/p>
瑙ｏ細
T(n) =
飪?/p>
飪?/p>
飪?/p>
飪?/p>
飪?/p>
飥?/p>
飥?/p>
飥?/p>
飥?/p>
1
)
1
(
)
(
)
2
(
2
1
)
1
(
n
n
n
T
n
褰?/p>
褰?/p>
飦?/p>
飦?/p>
飦?/p>
鎴?/p>
T(n) =
飪?/p>
飪?/p>
飪?
飪?/p>
飪?/p>
飥?/p>
飥?/p>
飥?/p>
1
)
(
)
2
(
2
1
)
1
(
n
n
n
T
n
褰?/p>
褰?/p>
飦?/p>
飦?/p>
2
锛?/p>
锛?/p>
5
鍒嗭級鐢ㄥ鐢ㄥ叕寮忔硶璁＄畻涓嬪垪閫掑綊鏂圭▼瑙ｇ殑娓愯繘闃躲�?/p>
T(n) =
飪?/p>
飪?
飪?/p>
飥?/p>
飥?/p>
飥?/p>
1
)
1
(
)
2
/
(
2
1
)
1
(
n
n
T
n
褰?/p>
褰?/p>
飦?/p>
飦?/p>
瑙ｏ細
鍥犱负
a=2, b=2
锛?/p>
鎵�浠?/p>
a
b
l
o
g
n
锛?/p>
2
log
2
n
锛?/p>
n
锛?/p>
鍙鐢ㄧ涓�绫绘儏鍐靛緱
(n)
T(n)
飦?/p>
飥?/p>
銆?/p>
3
锛?/p>
锛?/p>
4
鍒嗭級缁欏畾涓や釜搴忓垪
X=<A,B,C,B,D,A,B>
锛?/p>
Y=<B, D, C,A,B,A>
銆傝姹傚嚭
鍏舵渶闀垮叕鍏卞瓙搴忓垪銆?/p>
瑙?/p>
:
<B, C, B, A>
鎴?/p>
<B, C, A, B>
4
锛?/p>
锛?/p>
6
鍒嗭級瀵逛簬涓嬪垪鍚勭粍鍑芥暟
f (n)
鍜?/p>
g (n)
锛岀‘瀹?/p>
f (n) = O (g (n))
鎴?/p>
f (n) =
惟