动漫精品免费一区二区,久久国产操,国产免费AV在线

算法概念

查找是在大量的信息中尋找一個特定的信息元素，在計(jì)算機(jī)應(yīng)用中，查找是常用的基本運(yùn)算，例如編譯程序中符號表的查找。本文簡單概括性的介紹了常見的七種查找算法，說是七種，其實(shí)二分查找、插值查找以及斐波那契查找都可以歸為一類——插值查找。插值查找和斐波那契查找是在二分查找的基礎(chǔ)上的優(yōu)化查找算法

查找算法分類：

靜態(tài)查找和動態(tài)查找；
注：靜態(tài)或者動態(tài)都是針對查找表而言的。動態(tài)表指查找表中有刪除和插入操作的表。

無序查找和有序查找。
無序查找：被查找數(shù)列有序無序均可；
有序查找：被查找數(shù)列必須為有序數(shù)列。

平均查找長度（Average Search Length，ASL）：需和指定key進(jìn)行比較的關(guān)鍵字的個數(shù)的期望值，稱為查找算法在查找成功時(shí)的平均查找長度
對于含有n個數(shù)據(jù)元素的查找表，查找成功的平均查找長度為：ASL = Pi*Ci的和。
Pi：查找表中第i個數(shù)據(jù)元素的概率。
Ci：找到第i個數(shù)據(jù)元素時(shí)已經(jīng)比較過的次數(shù)。

排序方法條件時(shí)間復(fù)雜度(平均) 時(shí)間復(fù)雜度(最壞) 時(shí)間復(fù)雜度(最好)

順序查找無序 $O(n)$ $O(n)$ $O(1)$

分塊查找分塊順序 $O({log_2{n}})$ $O(n)$ $O({log_2{n}})$

二分查找有序 $O({log_2{n}})$ $O({log_2{(n+1)}})$ $O({log_2{(n+1)}})$

插值查找有序 $O({log_2{(log_2{n})}})$ $O({log_2{(log_2{n})}})$ $O({log_2{(log_2{n})}})$

斐波那契查找有序 $O({log_2{n}})$ $O({log_2{n}})$ $O({log_2{n}})$

二叉樹查找有序 $O({log_2{n}})$ $O(n)$ $O({log_2{n}})$

哈希表法(散列表) 無序 $O(1)$ $O(1)$ $O(1)$

排序方法	條件	時(shí)間復(fù)雜度(平均)	時(shí)間復(fù)雜度(最壞)	時(shí)間復(fù)雜度(最好)
順序查找	無序	$O(n)$	$O(n)$	$O(1)$
分塊查找	分塊順序	$O({log_2{n}})$	$O(n)$	$O({log_2{n}})$
二分查找	有序	$O({log_2{n}})$	$O({log_2{(n+1)}})$	$O({log_2{(n+1)}})$
插值查找	有序	$O({log_2{(log_2{n})}})$	$O({log_2{(log_2{n})}})$	$O({log_2{(log_2{n})}})$
斐波那契查找	有序	$O({log_2{n}})$	$O({log_2{n}})$	$O({log_2{n}})$
二叉樹查找	有序	$O({log_2{n}})$	$O(n)$	$O({log_2{n}})$
哈希表法(散列表)	無序	$O(1)$	$O(1)$	$O(1)$

七種算法

一、順序查找

線性搜索或順序搜索是一種尋找某一特定值的搜索算法，指按一定的順序檢查數(shù)組中每一個元素，直到找到所要尋找的特定值為止。是最簡單的一種搜索算法。順序查找也稱為線形查找，屬于無序查找算法。

算法描述

從數(shù)據(jù)結(jié)構(gòu)線形表的一端開始，順序掃描，依次將掃描到的結(jié)點(diǎn)關(guān)鍵字與給定值k相比較，若相等則表示查找成功；
若掃描結(jié)束仍沒有找到關(guān)鍵字等于k的結(jié)點(diǎn)，表示查找失敗。

代碼實(shí)現(xiàn)
/// 順序查找
/// @param array 查找數(shù)組
/// @param word 要查找關(guān)鍵字
- (NSInteger)sequentialSearch:(NSArray *)array searchWord:(id)word {
   for (int i = 0; i < array.count; i ++) {
       if ([array[i] isEqual:word]) {
           return I;
           break;
       }
   }
   return -1;
}
//調(diào)用
NSMutableArray * array = [NSMutableArray arrayWithObjects:@"15",@"6",@"106",@"236",@"2",@"34",@"13",@"58",@"37",@"121",@"33", nil];
NSLog(@"順序查找：%ld", [self sequentialSearch:array searchWord:@"58"]);
算法分析

假設(shè)一個數(shù)組中有n個元素，最好的情況就是要尋找的特定值就是數(shù)組里的第一個元素，這樣僅需要1次比較就可以。而最壞的情況是要尋找的特定值不在這個數(shù)組或者是數(shù)組里的最后一個元素，這就需要進(jìn)行n次比較。
查找成功時(shí)的平均查找長度為：（假設(shè)每個數(shù)據(jù)元素的概率相等） ASL = 1/n(1+2+3+…+n) = (n+1)/2
時(shí)間復(fù)雜度為O(n)，最好的情況是第一個就查找到了，為O(1)，最壞是沒有找到，為O(n)。

二、分塊查找

分塊查找又稱索引順序查找，它是順序查找的一種改進(jìn)方法。
將n個數(shù)據(jù)元素"按塊有序"劃分為m塊（m ≤ n）。每一塊中的結(jié)點(diǎn)不必有序，但塊與塊之間必須"按塊有序"；即第1塊中任一元素的關(guān)鍵字都必須小于第2塊中任一元素的關(guān)鍵字；而第2塊中任一元素又都必須小于第3塊中的任一元素，……

算法描述

先選取各塊中的最大關(guān)鍵字構(gòu)成一個索引表；

先對索引表進(jìn)行二分查找或順序查找，以確定待查記錄在哪一塊中；

然后，在已確定的塊中用順序法進(jìn)行查找。

代碼實(shí)現(xiàn)
/// 分塊查找
/// @param array 查找數(shù)組
/// @param indexItemList 索引表
/// @param number 要查找數(shù)字
- (NSInteger)blockSearch:(NSArray *)array indexItemList:(NSArray<BlockItem*> *)indexItemList searchNumber:(id)number {
   BlockItem *indexItem = nil;

   //遍歷索引表
   for(int i = 0;i < indexItemList.count; i++) {
   //找到索引項(xiàng)
       if(indexItemList[i].max >= number) {
           indexItem = indexItemList[I];
           break;
       }
   }
   
   //索引表中不存在該索引項(xiàng)
   if(indexItem == nil) {
       return -1;
   }
   //根據(jù)索引項(xiàng)，在主表中查找
   for(int i = indexItem.start; i < indexItem.start + indexItem.length; i++) {
       if(array[i] == number){
           return I;
           break;
       }
   }
   return -1;
}

//索引
@interface BlockItem : NSObject
@property (assign, nonatomic) int start;
@property (assign, nonatomic) int length;
@property (assign, nonatomic) NSNumber *max;
- (instancetype)initWithStart:(int)start length:(int)length max:(NSNumber *)max;
@end

@implementation BlockItem
- (instancetype)initWithStart:(int)start length:(int)length max:(NSNumber *)max {
   if (self = [super init]) {
       self.start = start;
       self.length = length;
       self.max = max;
   }
   return self;
}
@end

//調(diào)用
NSArray *blockArray = @[@3, @4, @6, @2, @5, @7, @14, @12, @16, @13, @19, @17, @25, @21, @36, @23, @22, @29];
BlockItem *model1 = [[BlockItem alloc] initWithStart:0 length:6 max:@7];
BlockItem *model2 = [[BlockItem alloc] initWithStart:6 length:6 max:@19];
BlockItem *model3 = [[BlockItem alloc] initWithStart:12 length:6 max:@36];
NSArray *indicesArray = @[model1, model2, model3];
NSLog(@"分塊查找：%ld", [self blockSearch:blockArray indexItemList:indicesArray searchNumber: @17]);
算法分析

分塊查找由于只要求索引表是有序的，對塊內(nèi)節(jié)點(diǎn)沒有排序要求，因此特別適合于節(jié)點(diǎn)動態(tài)變化的情況。
索引查找的比較次數(shù)等于算法中查找索引表的比較次數(shù)和查找相應(yīng)子表的比較次數(shù)之和，假定索引表的長度為m，子表長度為s，
則索引查找的平均查找長度為：
ASL= (1+m)/2 + (1+s)/2 = 1 + (m+s)/2
假定每個子表具有相同的長度，即s=n/m, 則 ASL = 1 + (m + n/m)/2 ,當(dāng)m = n/m ,(即m = ${log_2{n}}$ ，此時(shí)s也等于 ${log_2{n}}$ ), ASL = 1 + ${log_2{n}}$ 最小，時(shí)間復(fù)雜度為 $O({log_2{n}})$
可見，索引查找的速度快于順序查找，但低于二分查找。
在索引存儲中，不僅便于查找單個元素，而且更方便查找一個子表中的全部元素，若在主表中的每個子表后都預(yù)留有空閑位置，則索引存儲也便于進(jìn)行插入和刪除運(yùn)算。

三、二分查找

二分查找算法也叫折半法查找法，要求待查找的列表必須是按關(guān)鍵字大小有序排列的順序表。
二分查找基于分治思想，在實(shí)現(xiàn)上可以使用遞歸或迭代，首先用給定值k先與中間結(jié)點(diǎn)的關(guān)鍵字比較，中間結(jié)點(diǎn)把線形表分成兩個子表，若相等則查找成功；若不相等，再根據(jù)k與該中間結(jié)點(diǎn)關(guān)鍵字的比較結(jié)果確定下一步查找哪個子表，這樣遞歸進(jìn)行，直到查找到或查找結(jié)束發(fā)現(xiàn)表中沒有這樣的結(jié)點(diǎn)。

算法描述

將表中間位置記錄的關(guān)鍵字與查找關(guān)鍵字比較，如果兩者相等則表示查找成功；否則利用中間位置記錄將表分成前、后兩個子表。

如果中間位置記錄的關(guān)鍵字大于查找關(guān)鍵字，則進(jìn)一步查找前一個子表，否則查找后一個子表。

重復(fù)以上過程，一直到找到滿足條件的記錄為止時(shí)表明查找成功。

如果最終子表不存在，則表明查找不成功。

代碼實(shí)現(xiàn)
/// 二分法查找
/// @param array 查找數(shù)組
/// @param number 查找的數(shù)字
- (NSInteger)binarySearch:(NSArray *)array searchNumber:(id)number {
   NSUInteger mid;
   NSUInteger min = 0;
   NSUInteger max = array.count - 1;

   while (min <= max) {
         mid = (min + max)/2;
         if ([number intValue] == [array[mid] intValue]) {
           NSLog(@"We found the number! It is at index %lu", mid);
           return mid;
           break;
       } else if ([number intValue] < [array[mid] intValue]) {
           max = mid - 1;
       } else if ([number intValue] > [array[mid] intValue]) {
           min = mid + 1;
       }
   }
   return -1;
}
//調(diào)用
NSArray *binaryArray = @[@1,@20,@30,@45,@50,@55,@60,@66,@70];
NSLog(@"二分法查找：%ld", [self sequentialSearch:binaryArray searchWord:@30]);
算法分析

二分查找方法具有比較次數(shù)少、查找速度快及平均性能好的優(yōu)點(diǎn)。缺點(diǎn)是要求待查表為有序表，且插入、刪除困難。因此，折半查找方法適用于不經(jīng)常變動而查找頻繁的有序列表。
最壞情況下，關(guān)鍵詞比較次數(shù)為 ${log_2{(n+1)}}$ ，且期望時(shí)間復(fù)雜度為 $O({log_2{n}})$ ；

四、插值查找

插值查找是對二分查找的一種改進(jìn)，適用于均勻分布的有序表。思想基本上和二分查找一樣，有修改的地方就是mid的獲取。
在二分查找中，mid=(start+end)/2, 即mid=start+(end-start)/2;也就是說我們的mid每次都是折中的取，但是對于一些均勻分布的有序表，這樣做感覺有些費(fèi)時(shí)，比如找字典的時(shí)候，找a這個字母，我們肯定不會從中間開始，而是偏向于字典前面一些開始。
插值查找就是基于這樣的思想對mid取值進(jìn)行改進(jìn)。通過類比，我們可以將查找的點(diǎn)改進(jìn)為如下：
　　mid = start + (searchValue-array[start]) / (array[end]-array[start]) * (end-start)，
也就是將上述的比例參數(shù)1/2改進(jìn)為自適應(yīng)的，根據(jù)關(guān)鍵字在整個有序表中所處的位置，讓mid值的變化更靠近關(guān)鍵字searchValue，這樣也就間接地減少了比較次數(shù)。

算法描述

將表mid位置記錄的關(guān)鍵字與查找關(guān)鍵字比較，如果兩者相等則表示查找成功；否則利用中間位置記錄將表分成前、后兩個子表。

如果mid位置記錄的關(guān)鍵字大于查找關(guān)鍵字，則進(jìn)一步查找前一個子表，否則查找后一個子表。

重復(fù)以上過程，一直到找到滿足條件的記錄為止時(shí)表明查找成功。

如果最終子表不存在，則表明查找不成功。

代碼實(shí)現(xiàn)
/// 插值查找
/// @param array 查找數(shù)組
/// @param number 要查找數(shù)字
/// @param startIndex 查找起始位置
/// @param endIndex 查找結(jié)束位置
- (NSInteger)insertValueSearch:(NSArray *)array searchNumber:(id)number startIndex:(int)startIndex endIndex:(int)endIndex {
   
   if (endIndex >= startIndex) {
       int mid = startIndex + ([number intValue] - [array[startIndex] intValue]) / ([array[endIndex] intValue] - [array[startIndex] intValue]) * (endIndex - startIndex);
       if (array[mid] == number) {
           return mid;
       } else if (array[mid] > number) {
           return [self insertValueSearch:array searchNumber:number startIndex:startIndex endIndex:mid-1];
       } else if (array[mid] < number) {
           return [self insertValueSearch:array searchNumber:number startIndex:mid+1 endIndex:endIndex];
       }
   }
   return -1;
}
//調(diào)用
NSArray *insetValueArray = @[@1,@20,@30,@45,@50,@55,@60,@66,@70];
NSLog(@"插值查找：%ld", [self insertValueSearch:insetValueArray searchNumber:@70 startIndex:0 endIndex:(insetValueArray.count-1)]);
算法分析

查找成功或者失敗的時(shí)間復(fù)雜度均為 $O({log_2{(log_2{n})}})$ 。
對于表長較大，而關(guān)鍵字分布又比較均勻的查找表來說，插值查找算法的平均性能比折半查找要好的多。反之，數(shù)組中如果分布非常不均勻(如[@1,@2,@3,@201,@202,@203,@1000,@1001,@1003])，那么插值查找未必是很合適的選擇。

五、斐波那契查找

上面我們講了插值查找，它是基于折半查找改進(jìn)，然后除了插值方式的切割外，還有基于斐波那契黃金分割點(diǎn)切割方式的改進(jìn)。
所以斐波那契查找也是改變了二分查找中原有的中值 mid 的求解方式，其 mid 不再代表中值，而是代表了黃金分割點(diǎn)：
mid = left + F_{block - 1} - 1

算法描述

將表mid位置記錄的關(guān)鍵字與查找關(guān)鍵字比較，如果兩者相等則表示查找成功；否則利用中間位置記錄將表分成前、后兩個子表。

如果mid位置記錄的關(guān)鍵字大于查找關(guān)鍵字，則進(jìn)一步查找前一個子表，否則查找后一個子表。

重復(fù)以上過程，一直到找到滿足條件的記錄為止時(shí)表明查找成功。

如果最終子表不存在，則表明查找不成功。

代碼實(shí)現(xiàn)
#pragma mark 斐波那契查找
/// 斐波那契查找
/// @param array 查找數(shù)組
/// @param searchNumber 查找的數(shù)字
- (NSInteger)fibonacciSearch:(NSArray *)array searchValue:(id)searchNumber {
   NSMutableArray *mArray = [NSMutableArray arrayWithArray:array];
   NSArray *fibArray = [self fibonacciArray:30];
   int startIndex = 0;
   int endIndex = mArray.count - 1;
   
   int k = 0;
   
   while (endIndex > ([fibArray[k] intValue] - 1)) {
       k ++;
   }
   
   for (int i = mArray.count; i <= [fibArray[k] intValue]; i ++) {
       mArray[i] = mArray[endIndex];
   }
   
   while (startIndex <= endIndex) {
       int mid = startIndex + [fibArray[k - 1] intValue] - 1;   // 根據(jù)斐波那契數(shù)列進(jìn)行黃金分割
       if ([mArray[mid] intValue] == [searchNumber intValue]) {
           if (mid <= array.count - 1) {
               return mid;
           } else {
               // 說明查找得到的數(shù)據(jù)元素是補(bǔ)全值
               return array.count - 1;
           }
       } else if ([mArray[mid] intValue] > [searchNumber intValue]) {
               endIndex = mid - 1;
               k = k - 1;
       } else if ([mArray[mid] intValue] < [searchNumber intValue]) {
           startIndex = mid + 1;
           k = k - 2;
       }
   }
   return -1;
}

/// 獲得一個斐波那契數(shù)組
/// @param size 數(shù)組大小
- (NSArray *)fibonacciArray:(NSInteger)size {
   NSMutableArray *array = [NSMutableArray arrayWithCapacity:size];
   array[0] = @1;
   array[1] = @1;
   
   for (int i=2; i < size; i++) {
       array[i] = @([array[i-1] longLongValue] + [array[i-2] longLongValue]);
   }
   return array;
}
//調(diào)用
NSArray *fibonacciArray = @[@1,@3,@5,@7,@8,@10,@13,@15,@17,@19,@21];
NSLog(@"斐波那契查找：%ld", [self fibonacciSearch:fibonacciArray searchValue:@19]);
算法分析

在最壞情況下，斐波那契查找的時(shí)間復(fù)雜度還是 $O(log_2{n})$ ，且其期望復(fù)雜度也為 $O(log_2{n})$ ，但是與折半查找相比，斐波那契查找的優(yōu)點(diǎn)是它只涉及加法和減法運(yùn)算，而不用除法，而除法比加減法要占用更多的時(shí)間，因此，斐波那契查找的運(yùn)行時(shí)間理論上比折半查找小，但是還是得視具體情況而定。

六、二叉樹查找

二叉查找樹（Binary Search Tree，BST）是一種特殊的二叉樹，一棵二叉搜索樹（BST）是一棵二叉樹，其中，每個節(jié)點(diǎn)的值都要大于其左子樹中任意節(jié)點(diǎn)的值而小于右子樹中任意節(jié)點(diǎn)的值。

算法描述

如果二叉查找樹為空，則返回空操作，否則，執(zhí)行一下操作；

先取根節(jié)點(diǎn)，如果節(jié)點(diǎn) X 等于根節(jié)點(diǎn)，則返回；

如果節(jié)點(diǎn)小于根節(jié)點(diǎn)，則遞歸查找左子樹；如果節(jié)點(diǎn)大于根節(jié)點(diǎn)，則遞歸查找右子樹。

代碼實(shí)現(xiàn)
@interface Tree : NSObject
@property (strong, nonatomic) NSNumber *value;//值
@property (assign, nonatomic) int index;//下標(biāo)
@property (strong, nonatomic) Tree *left;//左樹
@property (strong, nonatomic) Tree *right;//右樹
- (instancetype)initWithValue:(NSNumber *)value index:(int)index left:(Tree *)left right:(Tree *)right;
@end

@implementation Tree
- (instancetype)initWithValue:(NSNumber *)value index:(int)index left:(Tree *)left >right:(Tree *)right {
   if (self = [super init]) {
       self.value = value;
       self.index = index;
       self.left = left;
       self.right = right;
   }
   return self;
}
@end

#pragma mark 二叉樹查找
/// 二分法查找
/// @param binaryTree 查找的二叉樹
/// @param number 查找的數(shù)字
- (NSInteger)binaryTreeSearch:(Tree *)binaryTree searchNumber:(id)number {
   Tree *tree = binaryTree;
   NSInteger index = -1;
   while (tree != nil) {
       if (number < tree.value) {
           tree = tree.left;
       } else if (number > tree.value) {
           tree = tree.right;
       } else if (number == tree.value) {
           index = tree.index;
       }
   }
   return index;
}
算法分析

最優(yōu)情況下，二叉搜索樹為完全二叉樹，其時(shí)間復(fù)雜度為：O( $log_2{n}$ )
最差情況下，二叉搜索樹為單支樹, ，其時(shí)間復(fù)雜度為：O(n)
一般的，二叉排序樹的查找性能在O( $log_2{n}$ )到O(n)之間。因此，為了獲得較好的查找性能，就要構(gòu)造一棵平衡的二叉排序樹，由此出現(xiàn)了2-3樹、紅黑樹、B樹、B+樹等。

七、哈希表法(散列表)

哈希查找是是一種以鍵-值(key-indexed) 存儲數(shù)據(jù)的結(jié)構(gòu)，我們只要輸入待查找的值即key，即可查找到其對應(yīng)的值。
哈希表查找又叫散列表查找，通過查找關(guān)鍵字不需要比較就可以獲得需要記錄的存儲位置，它是通過在記錄的存儲位置和它的關(guān)鍵字之間建立一個確定的對應(yīng)關(guān)系hashAddress，使得每個 key 對應(yīng)一個存儲位置 hashAddress(key)。若查找集合中存在這個記錄，則必定在 hashAddress(key) 的位置上。

算法描述

用給定的哈希函數(shù)構(gòu)造哈希表。

根據(jù)選擇的沖突處理方法解決地址沖突，常見的解決沖突的方法：拉鏈法和線性探測法

在哈希表的基礎(chǔ)上執(zhí)行哈希查找

代碼實(shí)現(xiàn)
#pragma mark 哈希查找
/// 哈希查找（未考慮沖突）
/// @param array 查找數(shù)組
/// @param number 要查找元素
- (NSInteger)hashSearch:(NSArray *)array searchNumber:(id)number {
   NSDictionary *hashTable = [self makeHashTable:array];
   if ([hashTable valueForKey:[NSString stringWithFormat:@"%@", number]]) {
       NSInteger index = [[hashTable valueForKey:[NSString stringWithFormat:@"%@", number]] integerValue];
       return index;
   }
   return -1;
}

- (NSDictionary *)makeHashTable:(NSArray *)array {
   NSMutableDictionary *hash = [NSMutableDictionary dictionary];
   for (int i = 0; i < array.count; i++) {
       if (![hash valueForKey:[NSString stringWithFormat:@"%d", i]]) {
           [hash setValue:[NSString stringWithFormat:@"%d", i] forKey:[NSString stringWithFormat:@"%@", array[i]]];
       }
   }
   return hash;
}
NSArray *hashArray = @[@1,@3,@5,@7,@8,@10,@13,@15,@17,@19,@21];
NSLog(@"哈希查找：%ld", [self hashSearch:hashArray searchNumber:@13]);
算法分析

單純論查找復(fù)雜度：對于無沖突的Hash表而言，查找復(fù)雜度為O(1)。
哈希表可以以極快的速度來查找、添加或刪除元素（只需要數(shù)次的比較操作。）它比紅黑樹、二叉搜索樹都要快得多。但是哈希表沒有排序功能，類似的，如尋找最大值、最小值、中值這些行為都不能在哈希表中實(shí)現(xiàn)。
哈希表的查找過程基本上和造表過程相同。一些關(guān)鍵碼可通過哈希函數(shù)轉(zhuǎn)換的地址直接找到，另一些關(guān)鍵碼在哈希函數(shù)得到的地址上產(chǎn)生了沖突，需要按處理沖突的方法進(jìn)行查找。在介紹的三種處理沖突的方法中，產(chǎn)生沖突后的查找仍然是給定值與關(guān)鍵碼進(jìn)行比較的過程。所以，對哈希表查找效率的量度，依然用平均查找長度來衡量。
查找過程中，關(guān)鍵碼的比較次數(shù)取決于產(chǎn)生沖突的多少。如果產(chǎn)生的沖突少，查找效率就高，如果產(chǎn)生的沖突多，查找效率就低。因此，影響產(chǎn)生沖突多少的因素，也就是影響查找效率的因素。影響產(chǎn)生沖突多少有以下三個因素：
　?、?哈希函數(shù)是否均勻；
　　② 處理沖突的方法；
　?、?哈希表的裝填因子。
分析這三個因素，盡管哈希函數(shù)的“好壞”直接影響沖突產(chǎn)生的頻度，但一般情況下，我們總認(rèn)為所選的哈希函數(shù)是“均勻的”。因此，可不考慮哈希函數(shù)對平均查找長度的影響。
哈希表的裝填因子定義為 α = $\frac{填入表中元素的個數(shù)}{哈希表的長度}$
是哈希表裝滿程度的標(biāo)志因子。由于表長是定值，α與“填入表中的元素個數(shù)”成正比，所以，α越大，填入表中的元素較多，產(chǎn)生沖突的可能性就越大；α越小，填入表中的元素較少，產(chǎn)生沖突的可能性就越小。
實(shí)際上，哈希表的平均查找長度是裝填因子α的函數(shù)，只是不同處理沖突的方法有不同的函數(shù)。下表為幾種不同處理沖突方法的平均查找長度:

處理沖突的方法 2+ 查找成功時(shí) 查找不成功時(shí)

線性探測法 H_nl = $\frac{1}{2}$ (1 + $\frac{1}{1 - α}$ ) U_nl = $\frac{1}{2}$ (1 + $\frac{1}{(1 - α)^2}$ )

二次探測法與再哈希法 H_nl = - $\frac{1}{α}ln{(1-α)}$ U_nl = $\frac{1}{1 - α}$

鏈地址法 H_nl = 1 + $\frac{α}{2}$ U_nl = α + $e ^{-α}$

哈希方法存取速度快、節(jié)省空間，靜態(tài)查找、動態(tài)查找均適用，但由于存取是隨機(jī)的，因此，不便于順序查找。

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av

姜小舟

算法概念

查找算法分類：

七種算法

一、順序查找

算法描述

代碼實(shí)現(xiàn)

算法分析

二、分塊查找

算法描述

代碼實(shí)現(xiàn)

算法分析

三、二分查找

算法描述

代碼實(shí)現(xiàn)

算法分析

四、插值查找

算法描述

代碼實(shí)現(xiàn)

算法分析

五、斐波那契查找

算法描述

代碼實(shí)現(xiàn)

算法分析

六、二叉樹查找

算法描述

代碼實(shí)現(xiàn)

算法分析

七、哈希表法(散列表)

算法描述

代碼實(shí)現(xiàn)

算法分析

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容

處理沖突的方法 2+	查找成功時(shí)	查找不成功時(shí)
線性探測法	H_nl = $\frac{1}{2}$ (1 + $\frac{1}{1 - α}$ )	U_nl = $\frac{1}{2}$ (1 + $\frac{1}{(1 - α)^2}$ )
二次探測法與再哈希法	H_nl = - $\frac{1}{α}ln{(1-α)}$	U_nl = $\frac{1}{1 - α}$
鏈地址法	H_nl = 1 + $\frac{α}{2}$	U_nl = α + $e ^{-α}$

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九 欧美,1769亚洲,黄色成人av

算法概念

查找算法分類：

七種算法

一、順序查找

算法描述

代碼實(shí)現(xiàn)

算法分析

二、分塊查找

算法描述

代碼實(shí)現(xiàn)

算法分析

三、二分查找

算法描述

代碼實(shí)現(xiàn)

算法分析

四、插值查找

算法描述

代碼實(shí)現(xiàn)

算法分析

五、斐波那契查找

算法描述

代碼實(shí)現(xiàn)

算法分析

六、二叉樹查找

算法描述

代碼實(shí)現(xiàn)

算法分析

七、哈希表法(散列表)

算法描述

代碼實(shí)現(xiàn)

算法分析

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av

一、順序查找

二、分塊查找

三、二分查找

四、插值查找

六、二叉樹查找