标签：... return int 复杂度 次方 算法 fun void

递归

普通情况，n只进行加减，多少的 n 次方，取决于返回几个

void fun(int n)
{
    ...
    return fun(n-1)
}

上面的就是 O(n)

void fun(int n)
{
    ...
    return fun(n-1) + fun(n-2);
}

上面的就是 O(2 n)，因为每次都是分裂成为两个，所以是 2 的 n 次方。

void fun(int n)
{
    ...
    return fun(n-1) + fun(n-2) + fun(n-3);
}

上面的就是 O(3 n)，因为每次都是分裂成为三个，所以是 3 的 n 次方。

特殊情况：n 涉及到乘除

void fun(int n)
{
    ...
    return fun(n / 2)
}

上面的就是 O(log2 n), 因为每次都要除以2，所以用几次，取决于 n 是 2 的多少次方，也就是以 2 为底，求 log.

循环

普通循环，n 只设计加减，n 的多少次方，取决于循环的层数

void fun()
{
    for (int i = 0; i < n + 1; i++) {}
}

上面就是 O(n)

void fun()
{
    for (int i = 0; i < n + 1; i++) {
        for (int j = 0; j < m - 1; m++) {}
    }
}

上面就是 O(n 2)，因为是两层循环，所以是 n 的平方。

特殊情况，n 涉及到乘除

void fun()
{
    for (int i = 0; i < (1 << n); i++) {}
}

上面就是 O(2 n)，因为 n 进行了移位的操作，所以相当于是 2 的 n 次方，所以结果就是 2 的n次方。

参数:

算法复杂度分析
https://www.cnblogs.com/gaochundong/p/complexity_of_algorithms.html

标签：...,return,int,复杂度,次方,算法,fun,void
From： https://www.cnblogs.com/ramlife/p/16643849.html