1.1
n=15
1.2
- 证明：首先以θ定义可知其有自反性即 f(n)=θ(g(n)) => θ(f(n))=g(n),又对任意的f , g有f(n) + g(n)=θ( max( f(n) , g(n) ) ),故有 max ( f(n) , g(n) ) = θ( f(n) + g(n) );
1.3
- T(n)=T(n-1)+n;
T(n-1)=T(n-2)+n-1
…
T(1)=T(0)+1;
以上n式相加有 T(n)=T(0) +n(n+1)/2
O(T(n))=O( n^2)
2.1
设置两个指针fast和slow分别沿着链表移动，令slow每次移动一格，fast每次移动两格，若单向链表有环，则在此后的某一时间两个指针必将相遇
fast=fast->next->next;
slow=slow->next;
时间复杂度为O（n）
空间复杂度为O（1）
2.2
（1）在第i个用该额外的指针指向第2i个，若不存在第2i个则将该指针置为null
伪代码：
if（i>当前位置&&额外指针不为空）
{
if（i<额外指针所指的位置）
转向next指向位置
else
转向额外指针所指位置
}
重复上述操作直到找到第i个
（2）相当于二分查找，时间复杂度为O（logn）
网友评论