一、叉排序樹(shù)的ASL
叉排序樹(shù)的ASL是平均查找長(zhǎng)度,在查找運(yùn)算中,由于所費(fèi)時(shí)間在關(guān)鍵字的比較上,所以把平均需要和待查找值比較的關(guān)鍵字次數(shù)稱(chēng)為平均查找長(zhǎng)度。一個(gè)算法的ASL越大,說(shuō)明時(shí)間性能差,反之,時(shí)間性能好,這也是顯而易見(jiàn)的。
在順序查找(Sequence Search)表中,查找方式為從頭掃到尾,找到待查找元素即查找成功,若到尾部沒(méi)有找到,說(shuō)明查找失敗。所以說(shuō),Ci(第i個(gè)元素的比較次數(shù))在于這個(gè)元素在查找表中的位置,如第0號(hào)元素就需要比較一次,名列前茅號(hào)元素比較2次……第n號(hào)元素要比較n+1次。
折半查找(Binary Search),首先待查找表是有序表,這是折半查找的要求。在折半查找中,用二叉樹(shù)描述查找過(guò)程,查找區(qū)間中間位置作為根,左子表為左子樹(shù),右子表為右子樹(shù),,因?yàn)檫@顆樹(shù)也被成為判定樹(shù)(decision tree)或比較樹(shù)(Comparison tree)。查找方式為(找k),先與樹(shù)根結(jié)點(diǎn)進(jìn)行比較,若k小于根,則轉(zhuǎn)向左子樹(shù)繼續(xù)比較,若k大于根,則轉(zhuǎn)向右子樹(shù),遞歸進(jìn)行上述過(guò)程,直到查找成功或查找失敗。在n個(gè)元素的折半查找判定樹(shù)中,由于關(guān)鍵字序列是用樹(shù)構(gòu)建的,所以查找路徑實(shí)際為樹(shù)中從根節(jié)點(diǎn)到被查結(jié)點(diǎn)的一條路徑,因?yàn)楸容^次數(shù)剛好為該元素在樹(shù)中的層數(shù)。
哈希表中的ASL查找成功的平均查找長(zhǎng)度是指查找到哈希表中已有關(guān)鍵字的平均探測(cè)次數(shù)。而查找不成功的平均查找長(zhǎng)度是指在哈希表中找不到待查的元素,最后找到空位置元素的探測(cè)次數(shù)平均值。
延伸閱讀:
二、BFS的過(guò)程是什么
BFS的過(guò)程是首先訪問(wèn)起始結(jié)點(diǎn)v,接著訪問(wèn)頂點(diǎn)v的所有未被訪問(wèn)的鄰接結(jié)點(diǎn),然后對(duì)每個(gè)繼續(xù)進(jìn)行上述步驟,直到所有結(jié)點(diǎn)都被訪問(wèn)過(guò)為止,當(dāng)然,在訪問(wèn)過(guò)程中,需要使用一個(gè)隊(duì)列,然后類(lèi)似二叉樹(shù)的層次遍歷來(lái)訪問(wèn)。
BFS通俗的來(lái)講,就如通病毒擴(kuò)散一般蔓延。往往采用BFS求解迷宮問(wèn)題的入口到出口的最短路徑。