数据结构基本概念.docx

数据结构基本概念.docx

《数据结构基本概念.docx》由会员分享，可在线阅读，更多相关《数据结构基本概念.docx（13页珍藏版）》请在冰点文库上搜索。

数据结构基本概念

（1时间频度一个算法花费的时间与算法中语句的执行次数成正比例，哪个算法中语句执行次数多，它花费时间就多。

一个算法中的语句执行次数称为时间频度。

记为T（n。

n称为问题的规模。

例:

求下列算法的时间频度for（i=1;i<=n;i++for（j=1;j<=i;j++分析：

时间频度T（n=1+2+3+…+nn（n+1=2x=x+1;

（2时间复杂度设T（n的一个辅助函数为g（n,定义为当n大于等于某一足够大的正整数n0时，存在两个正的常数A和B（其中A≤B），使得A≤T（n/g（n≤B均成立，则称g（n是T（n的同数量级函数。

把T（n表示成数量级的形式为：

T（n=Ｏ（g（n其中Ｏ为Order（即数量级）的首字母。

例如：

若T（n=n（n+1/2,则有1/4≤T（n/n2≤1，故它的时间复杂度为Ｏ（n2,即Ｔ（n与n2数量级相同。

按数量级递增排列，常见的时间复杂度有：

在各种不同算法中，若算法中语句执行次数为一个常数，则时间复杂度为O（1

2空间复杂度（1空间频度一个算法在执行时所占有的内存开销，称为空间频度.（２空间复杂度与时间复杂度类似，空间复杂度是指算法在计算机内执行时所占用的内存开销规模。