数据结构基础知识学习（一）

程序设计 &＃61; 数据结构&＃43;算法

基本概念&＃xff1a;

• 数据&＃xff1a;描述客观事物的符号&＃xff0c;是计算机中可以操作的对象&＃xff0c;能被计算机识别&＃xff0c;并输入给计算机处理的符号的集合。
• 数据元素&＃xff1a;是组成数据的&＃xff0c;有一定意义的基本单位&＃xff0c;在计算机中通常作为整体处理&＃xff0c;也被称为记录。
• 数据项&＃xff1a;一个数据元素可以有若干个数据项组成。数据项是数据不可分割的最小的单位。

数据结构&＃xff1a;

概念&＃xff1a;相互之间存在一种或者多种特定关系的数据元素的集合。

算法&＃xff1a;

概念&＃xff1a;解决特定问题求解步骤的描述。在计算机中表现为指令的有限序列&＃xff0c;每条指令可表示一条或多个操作。

算法的特性&＃xff1a;

• 输入&＃xff1a;算法具有零个或者多个输入。
• 输出&＃xff1a;只有一个或多个输出。
• 有穷性&＃xff1a;算法在执行有限的步骤之后&＃xff0c;自动结束而不会出现无限循环&＃xff0c;并且一个步骤可接受的时间内完成。
• 确定性&＃xff1a;算法的每一步骤都有确定的含义&＃xff0c;不会出现二义性。
• 可行性&＃xff1a;算法的每一步都是必须可行的&＃xff0c;也就是说&＃xff0c;每一步都能够通过执行有限次数完成。

算法分析的分类&＃xff1a;

算法存在最好、平均和最坏的情况&＃xff1a;

• 最坏情况&＃xff1a;任意输入规模的最大运行次数&＃xff08;上界&＃xff09;这是我们常常关注的情况。
• 平均情况&＃xff1a;任意输入规模的期望运行次数。
• 最好情况&＃xff1a;任意输入规模的最小运行次数&＃xff0c;通常最好情况不会出现&＃xff08;下界&＃xff09;

算法的复杂度&＃xff1a;时间复杂度和空间复杂度

1、时间复杂度之大O渐进表示法

一个算法语句总的执行次数是关于问题规模N的某个函数&＃xff0c;记为f&＃xff08;N&＃xff09;&＃xff0c;N称为问题的规模。语句总的执行次数记为T&＃xff08;N&＃xff09;当N不断变化时&＃xff0c;T&＃xff08;N&＃xff09;也在变化&＃xff0c;算法执行次数的增长速率和f&＃xff08;N&＃xff09;的增长速率相同。
则有 T&＃xff08;N&＃xff09;&＃61; O&＃xff08;f&＃xff08;N&＃xff09;&＃xff09;&＃xff0c;称为O&＃xff08;f&＃xff08;N&＃xff09;&＃xff09;为时间复杂度的大O渐进表示法。

2、一般算法O&＃xff08;N&＃xff09;的计算方法&＃xff1a;

1. 用常数1取代运行时间中的所有的加法常数。
2. 在修改后的运行次数函数中&＃xff0c;只保留最高阶。
3. 如果最高阶项系数存在且不是1&＃xff0c;则去除与这个项相乘的常数。

时间复杂度典例&＃xff1a;

1、二分搜索算法的时间复杂度为O&＃xff08;logN/2&＃xff09;算法中把logN/2&＃61;lgN 。。。 M分搜索的算法时间复杂度为logN/M
2、递归算法时间复杂度&＃xff1a;递归总次数*每次递归的次数。递归算法的空间复杂度&＃xff1a;递归的深度*递归的空间的大小。

空间复杂度&＃xff1a;

函数中创建对象的个数关于问题规模函数表达式。一般情况下用O的渐进表示法表示。