# 那个函数增长的更快？$N\log N, N^{1+\xi /\sqrt{\log N}(\xi>0) }$

假设$N^{1+\xi /\sqrt{\log N} }<N\log N$, 则有$N^{\xi /\sqrt{\log N} }<\log N$
两边取对数，有$\frac{\xi}{\sqrt{\log N}}\log N <\log^{\log N}$
化简得$\xi\sqrt{\log N}<\log\log N$
令$N=\sqrt{\log N}$, 则有$\xi^2N<\log^2N$
令$f(N)=\xi^2N,g(N)=\log^2N$
由$\lim_{N\to\infty}\frac{f(N)}{g(N)}$ 可得极限为$\infty$
所以$g(N)=o(f(N))$
假设不成立，$N\log N$ 增长更慢

# 证明对任意常数$k$,$\log^kN=o(N)$

只考虑正整数，对$k=0,1$，基准情况成立
当$k_1<k_2$, 有$\log^{k1}N=o(\log^{k2}N)$
对于$k$, 仍有$\lim_{N\to\infty}\frac{\log^kN}{N}=0$, 所以对任意常数$k$, 有$\log^kN=o(N)$

# 求两个函数$f(N)$ 和$g(N)$，使得$f(N)\ne O(g(N))$ 且$g(N)\ne O(f(N))$

只要$\lim_{N\to\infty}\frac{f(N)}{g(N)}$ 的极限在$0$ 和$\infty$ 之间摆动即可
所以有$f(N)=\begin{cases} 1 & N\;is\;even\;number \\ N & N\;is\;odd\;number \end{cases}$ $g(N)=\begin{cases} N & N\;is\;even\;number \\ 1 & N\;is\;odd\;number \end{cases}$
类似摆动数列，只不过围绕着固定值摆动幅度加大

# 假设需要生成前$N$ 个自然数的一个随机置换。例如，{4，3，1，5，2} 和 {3，1，4，2，5} 就是合法的置换，但 {5，4，1，2，1} 却不是，因为数$1$ 出现两次而数$3$ 却没有。这个程序常常用于模拟一些算法。我们假设存在一个随机数生成器$RandInt(i,j)$，它以相同的概率生成$i$ 和$j$ 之间的一个整数。下面是三个算法。

• 1 如下填入从 $A[0]$ 到 $A[N-1]$ 的数组$A$; 为了填入$A[i]$, 生成随机数直到它不同于已经生成的 $A[0],A[1],...,A[i-1]$ 时，再将其填入$A[i]$。

int RandInt(int lower, int upper)

    {

        srand((unsigned)time(NULL));

        Sleep(500);// 滞后 0.5S

        return rand() % upper+lower;

    }

void Random(int *arr,int lower, int upper)

    {

        int i = 0;

        while (i < upper)

        {

            int temp = RandInt(lower, upper);

            BOOL flag = 1;

            for (int j = 0; j <=i; j++)

            {

                if(arr[j]==temp)

                {

                    flag = 0;

                }

            }

            if(flag)

            {

                arr[i] = temp;

                i++;

            }

        }

        for ( i = 0; i < upper; i++)

        {

            printf("%d ", arr[i]);

        }

    }

忽略掉打印语句，从最内层的$for$ 循环看起，每次至少执行$i$ 次
随机数产生的概率是等可能的，所以$while$ 语句每次循环产生不同随机数概率是$\frac{N-i}{N}$
即 $\sum_{i=0}^{N-1}$$\frac{Ni}{N-i}$$<$$\sum_{i=0}^{N-1}$$\frac{N^2}{N-i}$$<$$N^2\sum_{i=0}^{N-1}\frac{1}{N-i}$
假设以最坏情况运行，则可令$N-1=N,i=1$
所以$N^2\sum_{i=0}^{N-1}\frac{1}{N-i}$$<$$N^2\sum_{j=1}^{N}\frac{1}{j}$
由调和数$H_N = \sum_{i=1}^{N}\frac{1}{i}\approx\log_eN$ 得
$N^2\sum_{j=1}^{N}\frac{1}{j}$ $=$ $O(N^2\log N)$, 即该算法时间复杂度

• 2. 同算法 (1)，但是要保存一个附加的数组，称之为$Used$（用过的）数组。当一个随机数$Ran$ 最初被放入数组$A$ 的时候，置 $Used[Ran]=1$,。这就是说，当用一个随 机数填入$A[i]$ 时，可以进一步来测试该随机数是否已经被使用，而不是像第一个算法那样（可能）进行$i$ 步测试。

void Random1(int *arr,int lower, int upper)

    {

        int *used = (int*)malloc( upper*sizeof(int) );

        for ( int i = 0; i < upper; i++ )

        {

            used[i] = 0;

        }

        int i = 0;

        while (i < upper)

        {

            int temp = RandInt(lower, upper);

            if(used[temp-1]==0)

            {

                used[temp-1] =1;

                arr[i] = temp;

                i++;

            }

        }

        for ( i = 0; i < upper; i++)

        {

            printf("%d ", arr[i]);

        }

        free(used);

    }

该算法$while$ 语句中少了$for$ 循环
所以有$\sum_{i=0}^{N-1}i+\sum_{i=0}^{N-1}\frac{N}{N-i}$$<$$\sum_{i=1}^{N}i+N\sum_{j=1}^{N}\frac{1}{j}$$=$$O(N)+O(N\log N)$
即时间复杂度为$O(N\log N)$

• 3. 填写该数组使得 $A[i]=i+1$, 然后：

for(i=1;i<N;i++)

    Swap(&A[i]，&A[RandInt(0,i)]);

void Random2(int *arr,int lower, int upper)

    {

        // 装数

        for ( int i = 0; i < upper; i++)

        {

            arr[i] = i+1;

        }

        // 随机换数

        for ( int i = 1; i < upper; i++)

        {

            Swap(&arr[i], &arr[RandInt(0,i)]);

        }

        // 打印数

        for (int i = 0; i < upper; i++)

        {

            printf("%d ", arr[i]);

        }

    }

    void Swap(int *a,int *b)

    {

        int temp = *a;

        *a = *b;

        *b = temp;

    }

时间复杂度为线性$O(N)$

• a 证明这三个算法都生成合法的置换，并且所有的置换都是等可能的。
• b 对每一个算法给出你能够得到的尽可能准确的期望的运行时间分析 (用大 $O$)。
• c 分别写出程序来执行每个算法$10$ 次，得出一个好的平均值。
  对 $N=250,500,1000,2000$ 运行程序 $1$;
  对 $N=2500,5000,10000,20000,40000,80000$ 运行程序$2$;
  对 $N=10000,20000,40000,80000,160000,320000,640000$ 运行程序 $3$。

# 编写一个程序来确定正整数$N$ 是否是素数

• $1$ 是素数，
• 能被$2$ 整除的偶数和能被奇数整除的合数都不是素数，
• 凡是合数均有$num=part1*part2$, 且有且仅有一个$part$ 小于 $\sqrt{num}$。

int isPrime(unsigned int N)

    {

        if (N == 1)

            return 0;

        if (N % 2 == 0)

            return 0;

        if (N == 2)

            return 0;

        for (int i = 3; i*i <= N; i += 2)

        {

            if (N % i == 0)

                return 0;

        }

        return 1;

    }

$if$ 语句只执行一次，可视为常量，忽略不计
一共执行$\sqrt{N}$ 次，所以时间复杂度为$O(\sqrt{N})$

# 不用递归，写出快速求幂的程序

以$3^8$ 为例，$3^8=3^8*1$,$8=(1000)_2$
$(1000)_2$ 有$4$ 位，从第零位开始每右移一次，便开始循环平方一次，共四次
$3^2=3*3$，
$3^4=3^2*3^2$，
$3^8=3^4*3^4$，
$(1000)_2$ 只有一个$1$, 所以只进行一次乘法，即$3^8=3^8*1$
再以$3^{15}$ 为例，$3^{15}=3^8*3^4*3^2*3*1$,$15=(1111)_2$
这次$(1111)_2$ 有$4$ 个$1$, 所以进行四次乘法，有$3^{15}=3^8*3^4*3^2*3*1$

double Pow(double x, int n)

    {

        double result = 1;

        while (n)

        {

            if (n & 1)        //  等价于判断 n 的末位是不是 1

                result *= x;

            n >>= 1;          // 将 n 右移一位，即遍历原 n 的二进制的每一位

            x *= x;  //n 右移了一位，x 补上

        }

        return result;

    }

时间复杂度为$o(N)$

# 编写一个程序求解主要元素

思路:

• 1 找出主要元素的候补元 (也许没)
• 2 判断候补元是不是主要元素

有点类似最优起点算法，$major$ 记录候补元，$count$ 记录候补元出现次数，若$count<0$, 则重置$major$ 和$count$, 遍历整个数组之后再判断是否是主要元素

int MainElement(int*arr,int len)

{

    // 边界条件判断，如果数组为空就返回 - 1

    if(arr==NULL||len==0)

        return -1;

    // 先找出主要元素

    int major = arr[0];

    int count = 1;

    for(int i=1;i<len;i++)

    {

        if(arr[i]==major)

            // 如果当前元素等于 major，count 就加 1

            count++;

        else

            // 否则 count 就减 1，

            count--;

        if(count<0)

        {

            // 如果 count 小于 0，说明前面的

            // 全部抵消了，这里在重新赋值

            major = arr[i];

            count = 1;

        }

    }

    // 下面是判断主要元素是否存在

    count = 0;

    for(int i=0;i<len;i++)

    {

        if(major==arr[i])

        {

        	count++;

            if(count>(len>>1))

                return major;

        }

    }

    return -1;

}

时间复杂度为$O(N)$