泛型算法-1
泛型算法实现了一些经典算法的公共接口,如排序和搜索;称它们是“泛型的”,是因为它们可以用于不同类型的元素的和多种容器类型(不仅包括标准库类型,还包括内置的数组类型),以及其它类型的序列。
** 大多数算法都定义在头文件algorithm中 **
算法永远不会执行容器的操作
二分查找的基本思想: 将 n 个元素分成大致相等的两部分,取 a[n/2] 与 x(查找目标值) 做比较,如果
x == a[n/2]
,则找到 x,算法中止;否则,如果x < a[n/2]
,则只要在数组 a 的左半部分继续搜索 x,如果x > a[n/2]
, 则只要在数组 a 的右半部搜索 x。
使用二分查找算法的前提:待查找序列是有序的
由算法核心思想可知:每次对比都将下一步的比对范围缩小一半。每次比对后剩余数据项如下表:
即要找的元素正好在初始查找序列的中间一次比较出结果,时间复杂度为 $ O(1) $。
即比对范围只剩下 1 个数据项的情况这个数据项即为正要找的元素。这时,可求解如下方程组($ i $ 为比较次数):
$$ \frac{n}{2^i}=1 $$
时间复杂度为 $ O(log(n)) $
进行平均时间复杂度分析时需要讨论:随着元素个数n的增多,需要几步算法才能终止?查找成功有多少种情况?查找失败有多少种情况?
设 $ n=2^k-1 $, $ k $ 为比较次数。易知,对于 $$ t=1,2,…, \lfloor log(n) \rfloor + 1 $$, 会有 $ 2^{t-1} $ 个元素在 $ t $ 步之后使算法成功终止。总共有 $ (2n+1) $ 种情况,$ n $ 种情况为成功结束,$ (n+1) $ 种情况为失败终止。
由此可得二分搜索的平均比较次数为 $ (k = \lfloor log(n) \rfloor + 1) $:
$$ A(n)= \frac{1}{2n+1}(\sum_{i=1}^{k}i2^{i-1} + k(n+1)) $$
根据初等数学等差乘等比数列求和的错位相减法/裂项相消法。易知,
$$ \sum_{i=1}^{k}i2^{i-1} = 2^k(k-1)+1 $$
使用裂项相消法
由 $ \sum_{i=1}^{k}i2^{i-1} $,设 $ a_i=i2^{i-1},(i=1,…,k) $。注意到,$ a_i=(k-1)2^k-(k-2)2^{k-1} $。
$$ \sum_{i=1}^{k}i2^{i-1}=0\times2^1+1+1\times2^2-0\times2^1+2\times2^3-1\times2^2+…+(k-1)2^k-(k-2)2^{k-1}=2^k(k-1)+1 $$
$$ A(n)= \frac{1}{2n+1}(\sum_{i=1}^{k}i2^{i-1} + k(n+1)) $$
$$ \sum_{i=1}^{k}i2^{i-1} = 2^k(k-1)+1 $$
综上可得,$$ A(n) = \frac{1}{2n+1}((k-1)2^{k}+1+k2^k) $$
当 $ n $ 非常大时,可得
$$ A(n) \approx \frac{1}{2^{k+1}}((k-1)2^{k}+k2^k)=\frac{(k-1)}{2}+\frac{k}{2}=k-\frac{1}{2} $$
所以 $ A(n)<k=O(log(n)) $ ,平均时间复杂度为$ O(log(n)) $。
1 | # -*- coding: utf-8 -*- |
1 |
|
附:C++ 使用头文件typeinfo下的typeid(parameter).name()可获取参数获取类型名
* 使用class和struct定义类的唯一区别就是默认的访问权限 *]
定义在类内的成员函数是自动inline的
1 |
|
=default
保留默认的构造函数 & 构造函数初始值列表= default
1 |
|
1 |
|
初始化string对象的方式
初始化方式 | 说明 |
---|---|
string s1 | 默认初始化,s1是一个空字符串 |
string s2(s1) | s2是s1的副本 |
string s2=s1 | 等价于s2(s1),s2是s1的副本 |
string s3(“shansan”) | s3是字面值”shansan”的副本,除了字面值最后的那个空字符串外 |
string s3=”shansan” | 等价于s3(“shansan”) |
string s4(n,’c’) | 把s4初始化为由连续n个字符c组成的串 |
1 / 3