数据结构与算法分析

数据结构：大量数据的组织方法；

算法分析：算法运行时间的估算。涉及到计算效率。

设想，如果能把时间限制从16年减至不到1秒，不很神奇吗？

在很多问题中，一个重要的观念是：写出一个可以工作的程序并不够。如果这个程序在巨大的数据集上运行，运行时间就成了重要的 问题。

算法，是为求解一个问题需要遵循的、被清楚地指定的简单 指令的集合 。

对于一个问题，一旦给定某种算法，确定其是正确的，那么接下来重要的一步就是该算法花费的时间和空间等资源量 的问题

定义：如果存在正整数c和n0，使得当N>=n0时候，T(N)<=cf(N)，则记为T（N）=O（f(N)）（注意这里已经省去了常数c 的影响）

当我们说T(N)=Of((N))时候，我们是在保证函数T（N）是以不快于f(N)的速度增长；因此，f是T的一个上界。

如下：T（N）=O（2N2）或者T(N)=O(N2+N)，均是不合习惯的，应该表示为T（N）=O(N²)

运行时间计算例子：
计算一个i³求和的例子：

Sum(int N)
{
    int i, PartialSum;

    PartialSum = 0;           //1
    for (i = 1;i <= N;i++)    //2
        PartialSum += i*i*i;  //3
    return PartialSum;        //4
} 

声明不计时间，第1和第4行各占1个时间单元：1+1

第3行，4个运算；判断N次，4N；

第2行，初始化1+N+N（自增），2N+2；

总共：2+4N+2N+2=6N+4;因此，我们说该函数是O(N)

数据结构与算法分析

原文：http://www.cnblogs.com/skylover/p/7122979.html