算法导论第三版第一章习题

1.1-2 除速度外, 在真实环境中还可能使用哪些其他有关效率的量度 ?

Other than speed, what other measures of efficiency might one use in a real-world setting?

空间，硬件资源等。

1.1-4 前面给出的最短路径与旅行商问题有哪些相似之处? 又有哪些不同?

How are the shortest-path and traveling-salesman problems given above similar? How are
they different?

相似点: 找出最短路径

不同点: shortest-path 不一定经过所有点, 而traveling-salesman 得经过所有点

1.2-2 假设我们正比较插入排序与归并排序在相同机器上的实现, 对于规模为n的输入, 插入排序运行8*n^2, 而归并排序运行64*n*lg(n)步 <lg(n)表示log2(n)以下lg(n)含义都是如此>; 问对哪些n值, 插入排序优于归并排序?

Suppose we are comparing implementations of insertion sort and merge sort on the same
machine. For inputs of size n, insertion sort runs in 8n2 steps, while merge sort runs in 64n
lg n steps. For which values of n does insertion sort beat merge sort?

程序较优准则: 程序运行步数少即用时少;

8 n^2 < 64 n lg(n) --> n < 8 lg(n); 编程得: 2<=n<= 43 ;

C语言代码实现:

#include <cmath>
#include <cstdio>
using namespace std;
int main()
{
    printf("%f
", log2(1));
    for(int i=2; i< 100; i++)
    {
        if((double)(i) < 8.0*(log2(i*1.0)))
        {
            printf("%d
", i);
        }
        else
            continue ;
    } return 0;
}

1.2-3 n的最小值为何值时, 运行时间100n^2的一个算法在相同机器上快于运行时间为2^n 的另一个算法?

原理如上： 100 n^2 < 2^n; 解这个不等式可得n>= 15;

C++实现程序:

#include <cstdio>
typedef long long LL;
inline LL deal(LL a, LL b){
    LL ans= 1;
    while(b){
        if(b & 1) ans *=a; 
        b /= 2;
        a = a*a;
    }
    return ans;
}
using namespace std;
int main()
{
    for(int i=1; i<= 63; i++)
    {
        LL xiaob=deal(2, i);  
        LL xiaoa=100*i*i ; 
        if(xiaoa < xiaob)
        {
             printf ("%d
", i);
            return 0; 
        }
    }
}

思考题1-1 (运行时间比较) 假设求解问题的算法需要f(n)毫秒, 对下表中的每个函数f(n)和时间t, 确定可以在时间t内求解的问题的最大规模n

NewImage

Problems 1-1: Comparison of running times
For each function f(n) and time t in the following table, determine the largest size n of a
problem that can be solved in time t, assuming that the algorithm to solve the problem
takes f(n) microseconds.

lg(n)的算法执行时间需要f(n)毫秒, 1s等于1000ms, 则可以有后面公式;

1000/(lg n) <= 1; --> 1000<= lg(n); ==> 2^1000 =n

	1秒	1分钟	1小时	1天	1个月	1年	1个世纪
lgn	2^1000	2^60000	正无穷大	正无穷大	正无穷大	正无穷大	正无穷大
Sqrt(n)	10^6	4.29E+9	1.76E+13	9.01E+15
n	1000	60000	3600000	86400000	259000000	31104000000	3110400000000
nlgn	141	4896	204095	3.94E+6
n^2	32	245	1898	9296	50912	177584	1775838
n^3	11	40	113	443	638	3145	14598
2^n	10	16	22	27	32	35	42
n!	7	9	10	12	15	17	18

开立方计算器：http://www.838dz.com/calculator/1633.html