计算机要工作，首先要有数据，数据就是计算机加工和处理的对象；简单的分类一下，数据分为数值数据和非数值数据；数值数据主要应用于工程和科学计算；而非数值数据，比如声音，图像等在计算机中是以二进制形式存放在物理介质上。每个二进制位为一个bit，8个二进制位为一个byte(字节)。
要谈数据结构，就必须了解数据类型(即一组值的集合和定义在该集合上的一组操作的总称。)；数据类型分为原子数据类型和结构数据类型(复合数据类型)。所谓的结构数据类型就是指由原子数据类型或者由其他结构数据类型组成的数据类型。数据结构是指计算机存储组织数据的方式。数据结构的分类如下：线性结构(队列，链表，栈等等)；非线性结构(树和图)。
算法的设计取决于数据结构，而算法的实现依赖于数据结构。数据的操作是在数据结构之上定义的操作算法。所以说算法的设计离不开数据结构，但是，算法的设计也有本身的技巧和方法，下面是几种常见的算法设计策略：
1.贪婪算法
2.分治算法
3.动态规划法
4.回溯法
5.概率算法
一个算法设计出来之后，怎么样才知道效率如何，当然不能拿到机子上跑一遍吧，再说，即使拿到机子上跑一遍，因为机子配置等等原因，效率也是不一样的。所以要验证一个算法的效率如何一般都使用事前估计的方法。一个算法的好坏取决于两方面，第一：时间；第二：空间；所以把算法的复杂度分为时间复杂度和空间复杂度。这里简单介绍一下时间复杂度，空间复杂度可以类比。
代码如下：
for (int a = 0; a != num1; a++)
{
for(int b = 0; b != num2; b++)
{
num[a][b] = b;
}
}
上面的代码出现了循环语句的嵌套，所以时间复杂度为O(num1*num2)。
折半查找的算法代码如下：
Node* Find(const Type& x, Node* ptr)
{
if(ptr == NULL)
{
return NULL;
}
else if(x data)
return Find(x,ptr->leftChild);
else if(x > ptr->data)
return Find(x,ptr->rightChild);
else return ptr;
}
这个函数采用了递归的形式。 算法的时间复杂度为O(log2n)。
常见的程序时间复杂度总结如下：
1 大部分程序的大部分指令之执行一次，或者最多几次。如果一个程序的所有指令都具有这样的性质，我们说这个程序的执行时间是常数。
logN 如果一个程序的运行时间是对数级的，则随着N的增大程序会渐渐慢下来，如果一个程序将一个大的问题分解成一系列更小的问题，每一步都将问题的规 模缩减成几分之一 ，一般就会出现这样的运行时间函数。在我们所关心的范围内，可以认为运行时间小于一个大的常数。对数的基数会影响这个常数，但改变不会太 大：当N=1000时，如果基数是10，logN等于3；如果基数是2，logN约等于10.当N=1 00 000，logN只是前值的两倍。当N时原来的两倍，logN只增长了一个常数因子：仅当从N增长到N平方时，logN才会增长到原来的两倍。
N 如果程序的运行时间的线性的，很可能是这样的情况：对每个输入的元素都做了少量的处理。当N=1 000 000时，运行时间大概也就是这个数值；当N增长到原来的两倍时，运行时间大概也增长到原来的两倍。如果一个算法必须处理N个输入（或者产生N个输出）， 那么这种情况是最优的。
NlogN 如果某个算法将问题分解成更小的子问题，独立地解决各个子问题，最后将结果综合起来 ，运行时间一般就是NlogN。我们找不到一个更好的形容， 就暂且将这样的算法运行时间叫做NlogN。当N=1 000 000时，NlogN大约是20 000 000。当N增长到原来的两倍，运行时间超过原来的两倍，但超过不是太多。
N平方 如果一个算法的运行时间是二次的（quadratic），那么它一般只能用于一些规模较小的问题。这样的运行时间通常存在于需要处理每一对输入 数据项的算法（在程序中很可能表现为一个嵌套循环）中，当N=1000时，运行时间是1 000 000；如果N增长到原来的两倍，则运行时间将增长到原来的四倍。
N三次方 类似的，如果一个算法需要处理输入数据想的三元组（很可能表现为三重嵌套循环），其运行时间一般就是三次的，只能用于一些规模较小的问题。当N=100时，运行时间就是1 000 000；如果N增长到原来的两倍，运行时间将会增长到原来的八倍。
2的N次方 如果一个算法的运行时间是指数级的（exponential），一般它很难在实践中使用，即使这样的算法通常是对问题的直接求解。当N=20时，运行时间是1 000 000；如果增长到原来的两倍时，运行时间将是原时间的平方！
本站仅提供存储服务，所有内容均由用户发布，如发现有害或侵权内容，请
点击举报。
