Python编程四级 题库
通常问题的规模越大算法执行的时间就越长,算法执行时间的增长率和问题规模的增长关系,称为空间复杂度。
时间复杂度和空间复杂度的概念,本题是时间复杂度的描述,不是空间复杂度。
计算下面这段程序的时间复杂度为平方阶:O(n^2)。(?)
sum1=0
for i in range(101):
sum1+=i
时间复杂度为线性阶,计O(n)。
空间复杂度是指算法被编写成程序后,在计算机中运行时所需存储空间大小的度量,记作S(n),其中n为问题的规模或大小。
空间复杂度是指算法被编写成程序后,在计算机中运行时所需存储空间大小的度量,记作S(n),其中n为问题的规模或大小。
运行以下代码的时间复杂度为O(n^2)。
两个for语句不为嵌套,那么它们执行的时间复杂度只计算一个的就可以了,所以时间复杂度为O(n)。
对数组进行快速排序是利用分治的思想,整个排序过程可以递归进行,算法效率高效,是一种稳定的排序算法,时间复杂度为O(nlogn)。( )
快速排序是不稳定的排序算法。
如果执行算法所需的临时空间不会随变量的变化而变化,那么该算法的空间复杂度为一个常量。( )
如果执行算法所需的临时空间不会随变量的变化而变化,那么该算法的空间复杂度为一个常量O(1)。
时间复杂度是衡量算法效率的指标,指出算法解决问题执行的计算工作量和问题规模的关系。
小明用Python语言写了一个程序,计算从1加到n的总和,他分别用两种方法实现了这个功能:
# 方法一
total = 0 for i in range(1, n+1): total += i
# 方法二
total = n * (n+1) // 2
小明说,方法2比方法1快得多,因为方法1的时间复杂度是O(n+1),而方法2的时间复杂度是O(1)。( )
方法2比方法1快,但方法1的时间复杂度是O(n)。
时间复杂度是重复语句执行最多次数,但保留最高阶项,所以方法1的时间复杂度是O(n)。
时间复杂度为O(n)的程序,比时间复杂度为O(n2)的程序执行效率要高。( )
随着输入规模n的增大,O (n) 增长速度比 O (n2) 慢,即执行相同规模的任务,O (n) 时间复杂度的算法所需执行次数更少,效率更高 。
算法的时间复杂度反应了程序执行时间随问题规模增长而增长的量级,在很大程度上能很好地反映出算法的优劣。( )
算法的时间复杂度反应了程序执行时间随问题规模增长而增长的量级,在很大程度上能很好地反映出算法的优劣。
下面的Python程序的时间复杂度是否为O(n2)?( )
n = 1000 total = 0 for i in range(n): for j in range(i, n): total += 1 print(total)
时间复杂度是O(n2)。