鏁版嵁緇撴瀯絎叚绔犲簲鐢ㄩ鍙婄瓟妗圼7]_璺ㄨ€冪綉

聽聽聽聽聽聽 聽1錛庡湪涓€媯佃〃紺烘湁搴忛泦S鐨勪簩鍙夋悳绱㈡爲(binary search tree)涓?/span>,浠繪剰涓€鏉′粠鏍瑰埌鍙剁粨鐐圭殑璺緞灝?/span>S鍒嗕負3閮ㄥ垎錛氬湪璇ヨ礬寰勫乏杈圭粨鐐逛腑鐨勫厓绱犵粍鎴愮殑闆嗗悎Sl錛涘湪璇ヨ礬寰勪笂鐨勭粨鐐逛腑鐨勫厓绱犵粍鎴愮殑闆嗗悎S2錛涘湪璇ヨ礬寰勫彸杈圭粨鐐逛腑鐨勫厓绱犵粍鎴愮殑闆嗗悎S3銆?/span>S=S1鈭?/span>S2鈭?/span>S3銆傝嫢瀵逛簬浠繪剰鐨?/span>a鈭?/span>Sl,b鈭?/span>S2錛?/span>c鈭?/span>S3鏄惁鎬繪湁a鈮?/span>b鈮?/span>c涓轟粈涔堛€?a target="_blank">娓呭崕澶у 2000 鍥?/span>(10鍒?/span>)銆戙€?a target="_blank">姝︽眽澶у 2000 涓夈€?/span>3銆?/span>

銆€銆€銆愬弬鑰冪瓟妗堛€?/span>

銆€銆€璇ョ粨璁轟笉鎴愮珛銆傚浜庝換涓€a鈧?/span>A,鍙湪B涓壘鍒版渶榪戠鍏?/span>f銆?/span>a鍦?/span>f鐨勫乏瀛愭爲涓娿€傚浜庝粠f鍒版牴緇撶偣璺緞涓婃墍鏈?/span>b鈧?/span>B錛屾湁鍙兘f鍦?/span>b鐨勫彸瀛愭爲涓婏紝鍥犺€?/span>a涔熷氨鍦?/span>b鐨勫彸瀛愭爲涓婏紝榪欐椂a錛?/span>b錛屽洜姝?/span>a錛?/span>b涓嶆垚绔嬨€傚悓鐞嗗彲浠ヨ瘉鏄?/span>b<c涓嶆垚绔嬨€傝€屽浜庝換浣?/span>a鈭?/span>A,c鈭?/span>C鍧囨湁a<c銆?/span>

銆€銆€

銆€銆€2錛庤瘯璇佹槑,鍦ㄥ叿鏈?/span>n(n>=1)涓粨鐐圭殑m嬈℃爲涓?/span>,鏈?/span>n(m-1)+1涓寚閽堟槸絀虹殑銆傘€?a target="_blank">澶嶆棪澶у1998鍥?/span>(8鍒?/span>)銆?/span>

銆€銆€銆愬弬鑰冪瓟妗堛€?/span>

銆€銆€n涓粨鐐圭殑m嬈℃爲錛屽叡鏈?/span>n*m涓寚閽堛€傞櫎鏍圭粨鐐瑰錛屽叾浣?/span>n-1涓粨鐐瑰潎鏈夋寚閽堟墍鎸囷紝鏁呯┖鎸囬拡鏁頒負n*m-(n-1)=n*(m-1)+1銆傝瘉姣曘€?/span>

銆€銆€

銆€銆€3錛庡浜庝換浣曚竴媯甸潪絀虹殑浜屽弶鏍?/span>,鍋囪鍙跺瓙緇撶偣鐨勪釜鏁頒負n0,鑰屾鏁頒負2鐨勭粨鐐逛釜鏁頒負n2,璇風粰鍑?/span>n0鍜?/span>n2涔嬮棿鎵€婊¤凍鐨勫叧緋誨紡n0=f(n2).瑕佹眰緇欏嚭鎺ㄥ榪囩▼銆傘€?a target="_blank" class="keylink">澶嶆棪澶у 1998 浜?/span> (8鍒?/span>)銆?/span>

銆€銆€銆愬弬鑰冪瓟妗堛€?/span>

銆€銆€璇佹槑 璁懼害涓?/span>1鍜?/span>2 鍙婂彾瀛愮粨鐐規(guī)暟鍒嗗埆涓?/span>n0錛?/span>n1鍜?/span>n2錛屽垯浜屽弶鏍戠粨鐐規(guī)暟n涓?/span>n=n0+n1+n2 (1)

銆€銆€鍐嶇湅浜屽弶鏍戠殑鍒嗘敮鏁幫紝闄ゆ牴緇撶偣澶栵紝鍏朵綑緇撶偣閮芥湁涓€涓垎鏀繘鍏ワ紝璁?/span>B涓哄垎鏀€繪暟錛屽垯n=B+1銆傚害涓?/span>1鍜?/span>2鐨勭粨鐐瑰悇鏈?/span>1涓拰2涓垎鏀紝搴︿負0 鐨勭粨鐐規(guī)病鏈夊垎鏀紝鏁?/span>n=n1+2n2+1 (2)

銆€銆€鐢憋紙1錛夊拰錛?/span>2錛夛紝寰?/span>n0= n2+1銆?/span>

銆€銆€

銆€銆€4錛庡浜庝換鎰忎竴媯甸潪絀虹殑浜屽弶鏍?/span>T錛屾垜浠敤n0琛ㄧずT涓彾瀛愮粨鐐圭殑涓暟錛岀敤n2琛ㄧずT涓湁涓ゆ５闈炵┖瀛愭爲鐨勭粨鐐圭殑涓暟銆傦紙1錛夌粰鍑?/span>n0鍜?/span>n2鎵€婊¤凍鐨勫叧緋誨紡銆傦紙2錛夎瘉鏄庝綘鍦紙1錛変腑緇欏嚭鐨勫叧緋誨紡鎴愮珛銆傘€?a target="_blank" class="keylink">澶嶆棪澶у 1997 涓?/span> (10鍒?/span>)銆?/span>

銆€銆€銆愬弬鑰冪瓟妗堛€?/span>

銆€銆€鍙傝棰?/span>26銆?/span>

銆€銆€

銆€銆€5錛庤瘯姹傛湁n涓彾緇撶偣鐨勯潪婊＄殑瀹屽叏浜屽弶鏍戠殑楂樺害;銆愪腑縐戦櫌璁＄畻鎵€ 2000 浜斻€?/span> (5鍒?/span>)銆?/span>

銆€銆€銆愬弬鑰冪瓟妗堛€?/span>

銆€銆€璁懼畬鍏ㄤ簩鍙夋爲涓彾瀛愮粨鐐規(guī)暟涓?/span>n錛屽垯鏍規(guī)嵁瀹屽叏浜屽弶鏍戠殑鎬ц川錛屽害涓?/span>2鐨勭粨鐐規(guī)暟鏄?/span>n-1錛岃€屽畬鍏ㄤ簩鍙夋爲涓紝搴︿負1鐨勭粨鐐規(guī)暟鑷沖涓?/span>1錛屾墍浠ュ叿鏈?/span>n涓彾瀛愮粨鐐圭殑瀹屽叏浜屽弶鏍戠粨鐐規(guī)暟鏄?/span>n+(n-1)+1=2n鎴?/span>2n-1錛堟湁鎴栨棤搴︿負1鐨勭粨鐐癸級銆傜敱浜庡叿鏈?/span>2n(鎴?/span>2n-1)涓粨鐐圭殑瀹屽叏浜屽弶鏍戠殑娣卞害鏄?/span>log2(2n)+1( log2(2n-1)+1錛屽嵆茅log2n霉+1,鏁?/span>n涓彾緇撶偣鐨勯潪婊＄殑瀹屽叏浜屽弶鏍戠殑楂樺害鏄?/span>log2n霉+1銆傦紙鏈€涓嬪眰緇撶偣鏁?/span>>=2錛夈€?/span>