优酷土豆网站建设,iis 7.0 网站配置,wordpress卡蜜销售,重庆网站营销1 二分查找
1.1 重要概念
拟解决的问题#xff1a;判断某个区间是否包含某个元素#xff0c;无法确定区间中包含重复元素的具体位置#xff1b;使用条件#xff1a;查找的区间必须符合单调性#xff1b;本质#xff1a;采用分治思想#xff0c;将某个单调区间一分为二…1 二分查找
1.1 重要概念
拟解决的问题判断某个区间是否包含某个元素无法确定区间中包含重复元素的具体位置使用条件查找的区间必须符合单调性本质采用分治思想将某个单调区间一分为二保证留下的一半区间包含解舍弃的一半区间不包含解时间复杂度O(log2n)(2)计算方式二分查找每查找一次将原问题的规模n缩减到1/2最糟糕的情况为n1时二分查找获得结果此时二分查找的次数为$n/2^x1即即x log_2n$
1.2 应用场景
判断某个单调区间是否包含某个元素前面一堆1后面一堆0如1111100000查询最后一个1出现的位置特殊情况1前面一堆0后面一堆1如0000011111查询第一个1出现的位置特殊情况2 1.3 代码演示
// 1 3 5 7 9 10
int binary_search(int *arr, int n ,int x) {int head 0, tail n - 1, mid;while (head tail) {mid (head tail) 1;if (arr[mid] x) return mid;if (arr[mid] x) head mid 1;else tail mid - 1;}return -1;
}// 1111100000
int binary_search1(int *arr, int n) {int head -1, tail n - 1, mid; // 当查找区间的元素全0时为避免二义性定义head-1而不是head0while (head tail) {mid (head tail 1) 1; // 上取整否则会出现死循环if (arr[mid] 1) head mid; // mid 有可能是最后一个1出现的位置else tail mid -1;}// head tail -1 时代表未找到否则返回对应元素的位置return head;
}// 00000111111
int binary_search2(int *arr, int n) {int head 0, tail n, mid; // 当查找区间的元素全0时为避免二义性定义tailn而不是tailn-1while (head tail) {mid (head tail) 1;if (arr[mid] 1) tail mid; // mid 有可能是第一个1出现的位置else head mid 1;}// head tail n 时代表未找到否则返回对应元素的位置return head n ? -1 : head;
}2 三分查找
2.1 拟解决的问题
二分查找解决的是在单调序列中查找目标值的问题而三分查找则是确定函数在凹/凸区间上的极值点
2.2 算法描述 在函数f(x)的某个区间[l, r]上取2个分界点其中m1位于l的1/3处m2位于l的2/3处即$m1 l (r - l) / 3$$m2 r - (r - l) / 3$这两个点m1、m2把区间 [l, r] 分为3 个子区间。这里以凸函数即有最大值为例讨论若f(m1) f(m2)说明极值点位于[m1, r]区间内可以不必再考虑[l, m1]区间原因就是当f(m1) f(m2)时m1处于单调递增区间段故f(l) f(m1)若f(m1) f(m2)说明极值点位于[l, m2]区间内可以不必再考虑[m2, r]区间原因就是当f(m1) f(m2)时m2处于单调递减区间段故f(m2) f(r)这样每一轮迭代都会把查找范围限制在原来的2/3直到最终逼近极值点即l和r之间的差值接近无穷小三分查找的时间复杂度O(log3n)(3)二分查找的时间复杂度O(log2n)(2)尽管二者的复杂度级别一样但是二分查找的效率更高因为二分查找是在1/2的区域寻找值而三分查找是在2/3的区域寻找值参考博客三分查找ternary search及其示例 - 简书、二分查找和三分查找哪个快算法复杂度与常数无关复杂度分析的常见误区 - 知乎 2.3 代码演示
double three_point_search(double (*func)(double), double l, double r) {double m1, m2;int flag 0; // flag 0func 函数为凸函数flag 1func 函数为凹函数// 凹凸函数判断if (func((l r) / 2.0) (func(l) func(r)) / 2.0 ) flag 0;else flag 1;#define EPSL 1e-6if (!flag) {while (fabs(r - l) EPSL) {m1 l (r - l) / 3.0, m2 r - (r - l) / 3.0;if (func(m1) func(m2)) l m1;else r m2;}} else {while (fabs(r - l) EPSL) {printf(l %f, r %f\n, l, r);m1 l (r - l) / 3.0, m2 r - (r - l) / 3.0;if (func(m1) func(m2)) r m2;else l m1;}}#undef EPSLreturn l;
}3 哈希表 HashTable
3.1 介绍 基于数组的“随机访问”特性其可以通过下标快速地找到对应位置的元素然而这种通过int下标寻找任意类型元素的映射关系并不通用映射关系int→任意类型。所以为了拥有数组“快速访问”的特性以及在查找元素过程中具有任意类型到任意类型的映射关系哈希表就应运而生了。哈希表主要由**哈希函数** 和 **哈希冲突处理方法**两部分组成其中**哈希函数**完成任意类型到int的映射这儿用key-value来说明key为输入value为输出即key到value的映射但是这种映射关系并不唯一即不同的key可能会有相同的value存在若直接通过value来标记key的话就会有覆盖现象发生此时就会用到 **哈希冲突处理方法**。简单来讲哈希表Hash table也叫散列表是通过哈希函数将任意类型的数据转化成一个整型数字然后用这个整型数字对数组长度取余将其结果作为数组的下标然后把这组数据存储到对应下标的数组空间**数据存储过程**。在使用哈希表进行数据查询时就是再次通过哈希函数获取数组的下标然后使用这个下标直接访问对应位置的数组元素故哈希表查找数据的时间复杂度几乎为O(1)**数据查找过程**。什么是哈希表散列表 哈希表就是通过哈希函数将输入映射到数组的某个位置然后利用数组的“随机访问”特性进行快速查找通过哈希函数映射值来存放数据的数组就是哈希表。 为什么要使用哈希表 在几乎为O(1)的时间复杂度内快速查找元素在数组中的位置。与一般查找不同若直接在数组内查找某个元素需要从头遍历一次数组其时间复杂度为O(n)若使用二分查找每次都需要将待查找区间缩小一半其时间复杂度为O(logn) 哈希表、数组、链表的区别 为了具有数组“随机访问”的特性在哈希表中引入了哈希函数然而哈希函数的引入会出现哈希冲突比如“如果两个字符串在哈希表中对应的位置相同怎么办”而数组的容量又是有限的其中一种解决方案就是使用链表结构在哈希表的每个入口挂一个链表保存所有对应的字符串就OK了此时的哈希表就是一种数组链表组合的数据结构。
3.2 哈希散列函数
把任意长度的输入又叫做预映射 pre-image通过散列算法变换成固定长度的输出该输出就是散列值。这种转换是一种压缩映射也就是散列值的空间通常远小于输入的空间不同的输入可能会散列成相同的输出而不可能从散列值来唯一的确定输入值。简单的说就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数。
3.3 冲突处理方法
开放定值再哈希|散列拉链法建立公共溢出区
哈希hash散列表结构详解_hash的结构-CSDN博客
Hash算法_bkdrhash acm-CSDN博客
3.4 代码演示
// 哈希函数BKDRHash, 将 字符串类型 - int
// 冲突处理拉链法typedef struct Node {char *str;struct Node *next;
} Node;typedef struct HashTable {Node **data;int size;
} HashTable;Node *init_Node(char *str, Node *head) {Node *p (Node *)malloc(sizeof(Node));p-str strdup(str); // 深拷贝p-next head; // 头插法return p;
}HashTable *init_hash(int n) {HashTable *h (HashTable *)malloc(sizeof(HashTable));h-size n 1; // 哈希表的空间利用率一般为70%~90%当前利用率为50%h-data (Node **)calloc(h-size, sizeof(Node *));return h;
}int BKDRHash(char *str) {int seed 31, hash 0;for (int i 0; str[i]; i) hash hash * seed str[i];return hash 0x7fffffff;
}int insert(HashTable *h, char *str) {int hash BKDRHash(str);int ind hash % h-size;h-data[ind] init_Node(str, h-data[ind]); // 拉链法return 1;
}int search(HashTable *h, char *str) {int hash BKDRHash(str);int ind hash % h-size;Node *p h-data[ind];while (p strcmp(p-str, str)) p p-next;return p ! NULL;
}void clear_node(Node *head) {if (head NULL) return ;Node *p head, *q;while (p ! NULL) {q p-next;free(p-str);free(p);p q;}return ;
}void clear(HashTable *h) {if (h NULL) return;for (int i 0; i h-size; i) {clear_node(h-data[i]);}free(h-data);free(h);return ;
}
