Question

计算机算法题

已知有实现同一功能的两个实时算法，问题规模为n时，算法A运算次数为n^2+2n+50，算法B运算次数为20n+10^3（n>1）,假设有一现场要求程序响应时间为0.015秒，所用计算机每秒可执行操作10^5次。问在这条件下，这两个算法可解问题的规模（即n）各是多少？哪个算法更合适？说明理由。如果计算机每秒可执行次数为10^7次，则哪个算法更合适？

Answer 1

如果计算机每秒可执行操作10^5次，0.015*10^5=1500.
对于算法A：n^2+2n+50=1500，解为n=37
对于算法B：20n+10^3=1500，解为n=25
所以，在计算机每秒可执行操作10^5这个条件下算法A更合适。因为在程序响应时间0.015秒里，算法A可以解决n=37规模的问题，比算法B的n=25更大。

如果计算机每秒可执行次数为10^7次，则哪个算法B更合适。
0.015*10^7=150000.
对于算法A：n^2+2n+50=150000，解为n=386
对于算法B：20n+10^3=150000，解为n=7450
所以，在计算机每秒可执行操作10^7这个条件下算法更合适。因为在程序响应时间0.015秒里，算法B可以解决n=7450规模的问题，比算法A的n=386更大。