#C++初学记录（算法效率与度量）

时间性能

**算法复杂性函数：

\[ f(n)=n^2 +1000n+\log_{10}n+1000 $$**
当n的数据规模逐渐增大时，f(n)的增长趋势：

* 当n增大到一定值以后，计算公式中影响最大的就是n的幂次级最高的项，并且其他的常数项和低幂次项都可以忽略，我们更关注的是它是一个什么量级的算法，是线性的还是n方的，还是指数级的。

<font size=4 face="微软雅黑">**大O表示法**
* 函数f、g定义域为自然数，值域为非负实数集
* **定义：**如果存在正数c和$n_0$，使得对任意的$$ n \geq n_0 $$ 都有$$ f(n) \leq cg(n)。\]

大O表示法的单位时间

大O表示法的运算规则

加法规则： $$f_1(n)+f_2(n)=O(max(f_1(n),f_2(n)))$$

（最耗时的那一段。）
乘法规则： $$ f_1(n)·f_2(n)=O(f_1(n)·f_2(n)) $$

(适用于while、for等循环结构）
- 顺序结构，if结构，swith结构

for(int i=0;i<n;i++)

    for(int j=0;j<n;j++)

       k++;

嵌套循环中第一个和第二个for都是O(n)的时间复杂度，两者的乘积是：

\[\sum{n-1 \atop i=0}(n-i)=\frac{n(n-1)}{2}=O(n^2)
\]

算法渐进分析：大$\Omega$表达式

定义：如果存在正数c和$n_0$，使得对所有n$\geq n_0$，都有f(n)$\geq$cg(n)，

则称f(n)在集合$\Omega$(g(n))中，或f(n)=$\Omega$(g(n))
大O表示法和大$\Omega$表示法的唯一区别在于不等式的方向
采用大$\Omega$表示法时，最好找出在函数增值率的所有下限中那个最“紧”（即最大）的下界

增长率大小比较：$$\log_2n \leq n \leq n \log_2n \leq n^2 \leq 2^n$$

算法复杂性分析

例：顺序寻找k值

顺序从一个规模为n的一维数组中找出一个给定的k值
最佳情况 O(1)
- 数组的第一个元素就是k值
- 只需要检查第一个元素
最差情况 O(n)
- 数组的最后一个才是k
- 检查数组中所有的n个元素
如果等概率分布 O(n)
- k值出现在n个位置上的概率都是1/n
概率不等
- 出现在第一个位置的概率为1/2
- 出现在第二个位置上的概率为1/4
  
  -出现在其他位置的概率都是$ \frac {1-1/2-1/4}{n-2} $

巴特西