|
简述下列概念数据数据元素数据类型数据结构逻辑结构存储结构线性结构非线性结构 试举一个数据结构的例子叙述其逻辑结构存储结构运算三个方面的内容 常用的存储表示方法有哪几种? 设三个函数fgh分别为 f(n)=n+n+ g(n)=n+n h(n)=n+nlgn 请判断下列关系是否成立 () f(n)=O(g(n)) () g(n)=O(f(n)) () h(n)=O(n) () h(n)=O(nlgn) 设有两个算法在同一机器上运行其执行时间分别为n和n要使前者快于后者n至少要多大? 设n为正整数利用大O记号将下列程序段的执行时间表示为n的函数 () i=; k=; while(i<n) { k=k+*i;i++; } () i=; k=; do{ k=k+*i; i++; } while(i<n); () i=; j=; while(i+j<=n) { if (i>j) j++; else i++; } ()x=n; // n> while (x>=(y+)*(y+)) y++; () x=; y=; while(y>) if(x>) {x=x;y;} else x++; 算法的时间复杂度仅与问题的规模相关吗? 按增长率由小至大的顺序排列下列各函数 (/)n(/)n nn n n! n lgn nlgn n(/) 有时为了比较两个同数量级算法的优劣须突出主项的常数因子而将低次项用大O记号表示例如设T(n)=nlgn+n+=nlgn+O(n) T(n)=nlgnn=lgn+O(n) 这两个式子表示当n足够大时T(n)优于T(n)因为前者的常数因子小于后者请用此方法表示下列函数并指出当n足够大时哪一个较优哪一个较劣? () T(n)=nn+lgn () T(n)=n+n+lgn () T(n)=n+lgn () T(n)=n+nlgn |
