4(a)假设某一个算法的时间代价为 ,对于输入规模n,在某台计算机上实现并完成该算法的时间为t秒。现在另有一台计算机,运行速度为第一台的64倍,那么t秒内新机器上能完成的输入规模为多大? 3.8(b)根据大 O 和 Ω的定义,写出表达式 的上限和下限。请注意确定适当的c和 n0 。 3.12 写出下列平均情况下时间代价的Θ表示式。假设所有变量类型int: (a) a = b + c; d = a + e; (b) sum = 0; for (i = 0; i < 3; i++) for (j = 0; j < n; j++) sum ++; (c) sum = 0; for (i = 0; i < n*n; i++) sum ++; (d) for (i = 0; i < n-1; i++) for (j = i+1; j < n; j++) { tmp = A[i][j]; A[i][j] = A[j][i]; A[j][i] = tmp; } (e) sum = 0; for (i = 0; i <= n; i++) for (j = 1; j <= n; j*=2) sum ++; (f) sum = 0; for (i = 1; i <= n; i*=2) for (j = 1; j <= n; j++) sum ++; (g)假设数组A中含有n个元素,函数Random花的时间是常数值,sort需要执行nlogn步。 for (i = 0; i < n; i++) { for (j = 0; j < n; j++) A[i] = Random(n); sort(A, n); } (h)假设数组A中元素为从0到n-1的任意一个排列。 sum3 = 0; for (i = 0; i < n; i++) for (j = 0; A[j] != i; j++) sum3 ++; (i) sum = 0; if (EVEN(n)) for (i = 0; i < n; i++) sum ++; else sum = sum +n;