1.1

n=15

1.2

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

1. 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）