《第1章_算法概述_作业ppt课件》由会员分享，可在线阅读，更多相关《第1章_算法概述_作业ppt课件（6页珍藏版）》请在金锄头文库上搜索。
课后练习 算法分析题 1 1求下列函数的渐近表达式 1 3按照渐近阶从低到高的顺序排列以下表达式 1 4 假设某算法在输入规模为n时的计算时间为T n 3 2n 在某台计算机上实现并完成该算法的时间为t秒 现有另一台计算机 其运行速度为第一台的64倍 那么在这台新机器上用同一算法在t秒内能解输入规模多大的问题 若上述算法的计算时间改进为T n n2 其余条件不变 则在新机器上用t秒时间能解输入规模为多大的问题 若上述算法的计算时间进一步改为T n 8 其余条件不变 那么在新机器上用t秒时间能解输入规模多大的问题 1 设新机器用同一算法能够解输入规模为n1的问题 因此t 3 2n 3 2n1 64 解得 n1 n 6 2 n12 64n2 解得 n1 8n 3 因为T n 8 为常数 因此算法可以解任意规模的问题 1 6对于下列各组函数f n 和g n 确定f n O g n 或f n g n 或f n g n 并简述理由 logn2 logn 5 logn2 O n1 2 n log2n nlogn n logn 10 log10 log2n n logn 2n 100n2 2n O 3n End
