稳定的直接插入排序
基本思想:
我们将一个待排序序列分为有序区和无序区(一般开始的时候将第一个元素作为有序区,剩下的元素作为无序区),每次将无序区的第一个元素作为待插入记录,按大小插入到前面已经排好的有序区中的适当位置,直到记录全部插入完成为止。(如果待插入的元素与有序序列中的某个元素相等,则将待插入元素插入到相等元素的后面)
二分查找的基本思想: 将 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()可获取参数获取类型名
Problem Description |
---|
Your task is to Calculate a + b. Too easy?! Of course! I specially designed the problem for acm beginners. You must have found that some problems have the same titles with this one, yes, all these problems were designed for the same aim |
Input |
The input will consist of a series of pairs of integers a and b, separated by a space, one pair of integers per line. |
Output |
For each pair of input integers a and b you should output the sum of a and b in one line, and with one line of output for each line in input. |
Sample Input |
1 6 1 20 |
Sample Output |
7 21 |