第二章测试1.若,则。 ( )
A:错 B:对
答案:A
2.设为阶方阵。现用以下算法求。
算法:
For i = 1 to n do
For j = 1 to n do
= 0
For k = 1 to n do
输出
该算法的时间复杂度为( )。
A:
B:
C:
D:
答案:D
A:对任意NP-C,。
B:存在NP,。
C:对任意NP,。
D:存在NP-C,。
答案:C
A:
B:
C:
D:
答案:ACD
A:若在该问题中,机器数是一个固定常数,该算法是一个多项式时间算法。
B:若在该问题中,机器数是一个固定常数,该算法是一个指数时间算法。
C:若在该问题中,机器数可能随实例不同而变化,该算法是一个多项式时间算法。
D:若在该问题中,机器数可能随实例不同而变化,该算法是一个指数时间算法。
答案:AD