Algorithm Complexity¶

迭代与递归¶

迭代 Ieration¶

for 循环
while循环
嵌套循环

递归 Recursion¶

box

调用栈：¶

递归函数每次调用自身时候，系统都会为新开启的函数分配内存，以存储局部变量、调用地址和其他信息等。

尾递归¶

普通递归：当函数返回到上一层级的函数后，需要继续执行代码，因此系统需要保存上一层调用的上下文。

尾递归：递归调用是函数返回前的最后一个操作，这意味着函数返回到上一层级后，无需继续执行其他操作，因此系统无需保存上一层函数的上下文。

  /* 尾递归 */
int tailRecur(int n, int res) {
    // 终止条件
    if (n == 0)
        return res;
    // 尾递归调用
    return tailRecur(n - 1, res + n);
}

递归树¶

斐波那契数列：

时间复杂度¶

Notation 定义¶

\(\exists c,n_0,s.t.\forall n >n _0 ,T（N）\le cf(N), T(N) = O(f(N))\) \(f(N)是T(N)的上界\)
\(\exists c,n_0,s.t.\forall n >n _0 ,T（N）\ge cg(N), T(N) = \Omega(g(N))\) \(g(N)是T(N)的下界\)
等且仅当\(T(N) = O(h(N))且T(N） = \Omega(h(N))\)时, \(T(N) = \Theta(h(N))\)
如果\(T(N) = O(p(N))且T(N)\ne\Theta(p(N))\),则\(T(N) = o(p(N))\) 法则
for 循环：最大为循环内语句包括测试的运行时间乘以迭代次数 for (int i = 0; i <= N; i++)初始化占1个时间单元，测试占N + 1个时间单元，赋值占N个时间单元，因此总共2N + 2 个时间单元
嵌套for循环：该语句的运行时间乘以该组所有for 循环的大小的乘积
顺序语句：各个语句的运行时间求和（其中语句的最大值就是所得时间）
if/else语句：最大为判断时间+分支中运行时间较长者

函数渐近上界¶

推算方法：忽略常数数，省略所有系数，循环嵌套时使用乘法，判断渐仅上界
常见类型：
幂次阶\(O(N^a)\)多出现在嵌套循环中
指数阶\(O(a^N)\)多出现在递归函数中
对数阶\(O(logN)\)

#include<stdio.h>
int main()
{
    int n = 0;
    int h = 0;
    int max = 0;
    int flag = 0;
    scanf("%d %d", &n, &h);
    int N = 100000;
    int bal[N];
    for(int i = 0; i < n; i++)
    {
        scanf("%d", &bal[i]);
    }
    for(int i = bal[0] - h; i <= bal[n-1]; i++)
    {
        int con = 0;
        for(int j = 0; j < n; j++)
        {
            if(bal[j] <= i + h && bal[j] >= i)
            {
                con ++;
            }
            if(con > max)
            {
                max = con;
                flag = i;
            }
        }
    }
    printf("%d %d", flag, max);
    return 0;
}

空间复杂度¶

推算方法¶

Notice：递归函数需要注意统计栈帧空间： - 在一个for loop中调用了N次 function() ，每轮中的 function() 都**返回并释放**了栈帧空间，因此空间复杂度仍为\(O(1)\)。 - 递归函数 recur() 在运行过程中会同时存在\(n\)个**未返回**的 recur() ，从而占用 \(O(N)\)的栈帧空间。

常见类型¶

常数阶\(O(1)\)：数量与输入数据大小\(N\)无关的常量、变量、对象。在循环中初始化变量或调用函数而占用的内存，在进入下一循环后就会被释放，因此不会累积占用空间，空间复杂度仍为\(O(1)\)
线性阶\(O(N)\):
- 元素数量与\(N\)成正比的数组、链表、栈、队列等。
- 递归深度为\(N\)的递归函数。

Solution for the Maximum Subsequence Sum¶

int max_subsequence_sum(int a[], unsigned int n)
{
    int thisssum = 0;
    int maxsum = 0;
    int best_i = -1, best_j = -1;
    for(int j = 0; j < n; j++)
    {
        thissum += a[j];
        if(thissum > maxsum)
        {
            maxsum = thissum;
            best_i = i;
            best_j = j;
        }
        if(thissum < 0)
        {
            i = j + 1;
            thissum = 0
        }
    }
    return maxsum;
}