算法的分析
定义:通常来说我们想要度量算法的运行时间
表达方式:把运行时间描述成一个输入规模的函数
输入规模可以是待排序的数组的规模,输入元素的数量等
具体算法:针对每行代码,计算出代价和次数,并加权求总
- 代价: ci代表第i行代码执行所需要的时间。(它是一个常量)
-
次数: 执行/循环的次数 (当一个for 或者 while循环按正常方式退出时,执行测试的次数比执行循环体的次数多1)
次数是一个关于输入规模n的函数,
通常我们考虑最坏的情况和平均情况的分析。
增长量级
专注于最坏情况下的n的最高阶
*因为当n足够大的时候,常量c和低阶n的影响没有那么大。
练习
2.2-1
Θ(n^3)
2.2-2
MY-SWAP(A)
for i = 1 to A.length - 1
min = i
for j = i+1 to A.length
if A[j] < A[min]
min = j
minA = A[j]
A[j] = A[i]
A[i] = minA
return A
2.2-3
MY-ADD(A, B)
C[1] = 0 // 平均和最差情况都是1步
for i = 1 to n // 平均情况:(1+2+...+n)/n = (1+n)/2 ; 最差情况:n
C[i] = (A[i] + B[i] + C[i]) % 2 // 同上
C[i+1] = (A[i] + B[i] + C[i]) / 2 // 同上
return C // 平均和最差情况都是1步
平均情况下: T(n) = (1+n)/2 + 2 = n/2 + 2.5 也就是说 Θ(n)
最差情况下: T(n) = n*3 + 2 也就是说 Θ(n)
2.2-4
让算法的增长量级尽量控制在低阶的情况下
网友评论