一、算法复杂度
【2011】设 n 是描述问题规模的非负整数，下面的程序片段时间复杂度是（）
x = 2;
while (x < n/2 ) x = 2*x;
A O( log2(n) ) B O( n ) C O( nlog2(n) ) D O( n^2 )
答案：Ａ
解析：
x = 2^i = n/2
i = log2( n/2 )
【2012】求整数 n ( n>= 0 ) 的阶乘的算法如下，其时间复杂度（）
int fact( int n ) {
if( n<= 1 ) return 1;
return n * fact( n-1 );
}
A O( log2(n) ) B O(n) C O( n*log2(n) ) D O( n^2 )
答案：B
解析：
递归，O(n) 复杂度。
【2013】已知两个长度分别为 n 和 m 升序链表，若将它们合并为一个长度为 m+n 的降序链表，则最坏情况的时间复杂度（）
A O(n) B O(nm) C O( min(m,n) ) D O( max(m,n) )
答案：D
解析：
前半段 O( n ) , 后半段 O( m - n ) , 故 O（max(m,n)）
【2014】下列程序段时间复杂度是（）
count=0;
for (k=1; k<=n; k *= 2)
for(j=1; j<=n; j++)
count++;
A O( log2(n) ) B O( n ) C O( n*log2(n) ) D O( n^2 )
答案：C
解析：
外层 log2(n), 内层 n 。复杂度 O( n*log2(n) )
【2017 】下列函数时间复杂度是（）
int func( int n ) {
int i=0, sum=0;
while (sum<n) sum += ++i;
return i;
}
A O(log2(n)) B O(n^0.5) C O( n ) D O( n*log2(n) )
答案：B
解析：
sum = i(i + 1)/2 < n （循环条件）
因此， i^2 < n， i = n^0.5
408真题
【2010】数组倒置。
答案：
【2011】 找中位数
答案：
【2013】输出主元素，主元素是个数超过一半的元素。
答案：
【2018】找出数组中的最小正整数。
答案：
【2016】线性链表，如何删除一个结点？
答案：D
【2016】线性链表物理寻址。
答案：D
【2009】倒数 K 个位置，注意指针。
答案：
解答：
【】
【】
ShoelessCai.com 值得您的关注！