假设sqrt(n)函数中涉及的算法时间复杂度为O(1)，那么下面的算法是判断n是否为素数，其时间复杂度为（ ）。void prime(int n){ for (i=2; isqrt(n) (n % i)!=0; i++) ; if (isqrt(n)) printf(%d is a prime number, n); else printf(%d is not a prime number, n);}
A: O(n)
B: O(1)
C: O(sqrt(n)) sqrt表示对n取根方
D: O(n-i)
A: O(n)
B: O(1)
C: O(sqrt(n)) sqrt表示对n取根方
D: O(n-i)
举一反三
- 下面程序段的时间复杂度是（ ）i=s=0;while(s<n){i++;s+=i;}? O(n)|O(s)|O(sqrt(n))|O(n^2)
- 以下算法的时间复杂度为（ ）。if (n >= 0) { for(int i = 0; i < n; i++) for(int j = 0; j < n; j++) printf("输入数据大于等于零\n"); } else { for(int j = 0; j < n; j++) printf("输入数据小于零\n"); } A: O(1) B: O(n*n+n) C: O(n) D: O(n*n)
- 计算下列程序段时间复杂度:inti=1;while(i<=n)i*=2 A: O(log(n)); B: O(n) C: O(2n) D: O(sqrt(n))
- 求时间复杂度：x=0;for(i=1; i<n; i++){ for (j=1; j<=n-i; j++){x++; }} A: O(n) B: O(n^2) C: O(1) D: O(√n )
- inti，sum=0；for（i=1；i<=n*n；i++）{sum+=i；}若n是问题的规模，则该算法的时间复杂度不是（） A: O（n） B: O（n*n） C: O（1） D: O（n*n*n）