题目
16.下面说法错误的是( )。(1)算法原地工作的含义是指不需要任何额外的辅助空间。(2)在相同的规模 n 下,复杂度 O(n)的算法在时间上总是优于复杂度 O(2n)的算法。(3)所谓时间复杂度是指最坏情况下,估算算法执行时间的一个上界。(4)同一个算法,实现语言的级别越高,执行效率就越低。A. (1)B. (1)、(2)C. (1)、(4)D. (3)
16.下面说法错误的是( )。(1)算法原地工作的含义是指不需要任何额外的辅助空间。(2)在相同的规模 n 下,复杂度 O(n)的算法在时间上总是优于复杂度 O(2n)的算法。(3)所谓时间复杂度是指最坏情况下,估算算法执行时间的一个上界。(4)同一个算法,实现语言的级别越高,执行效率就越低。
A. (1)
B. (1)、(2)
C. (1)、(4)
D. (3)
题目解答
答案
C. (1)、(4)
解析
步骤 1:分析(1)项
算法原地工作的含义是指额外空间相对于问题的规模(输入数据量)来说是个常数,而不是不需要任何额外的辅助空间。因此,(1)项是错误的。
步骤 2:分析(2)项
在相同的规模 n 下,复杂度 O(n)的算法在时间上总是优于复杂度 O(2n)的算法。这是正确的,因为 O(n) 的增长速度比 O(2n) 慢。
步骤 3:分析(3)项
所谓时间复杂度是指最坏情况下,估算算法执行时间的一个上界。这是正确的,因为时间复杂度通常是在最坏情况下的计算。
步骤 4:分析(4)项
同一个算法,实现语言的级别越高,执行效率就越低。这个结论不是绝对的,要看具体情况而定,一般情况下是这样的。因此,(4)项是错误的。
算法原地工作的含义是指额外空间相对于问题的规模(输入数据量)来说是个常数,而不是不需要任何额外的辅助空间。因此,(1)项是错误的。
步骤 2:分析(2)项
在相同的规模 n 下,复杂度 O(n)的算法在时间上总是优于复杂度 O(2n)的算法。这是正确的,因为 O(n) 的增长速度比 O(2n) 慢。
步骤 3:分析(3)项
所谓时间复杂度是指最坏情况下,估算算法执行时间的一个上界。这是正确的,因为时间复杂度通常是在最坏情况下的计算。
步骤 4:分析(4)项
同一个算法,实现语言的级别越高,执行效率就越低。这个结论不是绝对的,要看具体情况而定,一般情况下是这样的。因此,(4)项是错误的。