算法时间复杂度分析

各位\(CnBlogs\)的朋友们大家好, 我是蒟蒻\(Algo-3F\), 这是我的第一篇\(Blog\), 请多指教.

什么是算法时间复杂度

在不同的机器上, 代码运行时间是不同的, 比如说我手里这个去年的\(i9\)拯救者, 可能很快就跑出来了, 但是放在跟我一样大的\(i3\)上可能就很慢, 但是不难发现, 随着算法的改变, 运行时长好像是成比例的. 那么这个比例是什么? 就是算法时间复杂度.

怎么分析算法时间复杂度

一般循环的时间复杂度

比如这个代码,

for (int i(1); i <= n; i++)
{
    cout << "I AK IOI" << endl;
}

可以看到\(1\)个\(for\)循环, 循环变量是\(1 \sim n\)的, 那么算出运行时间就是\(t = \frac{代码长度}{CPU速度} = \frac{n}{V_{CPU}}\).
注: 真实的代码长度\(\ge\)看到的代码长度, 循环需要展开来看, 递归较复杂, 稍后讨论.

特殊循环的时间复杂度

比如这个计算\(\log(n)\)的代码,

for (cin >> n; n; n >>= 1)
{
    ans++;
}

通过位运算右移的手算得出, \(i = 0\)之前, 总共有过\(\log(i)\)次循环, 则循环时间复杂度为\(\log(n)\).

其他情况可以尝试自己手算, 并不难.

递归的时间复杂度

比如这个计算\(n!\)的代码,

int fctrl(int n)
{
    if (n == 0)
    {
        return 1;
    }
    else if (n == 1)
    {
        return 1;
    }
    else
    {
        return n * fctrl(n - 1);
    }
}

可以通过手算记录, 得到总共运行了\(n\)次的结论.

从代码时间复杂度到算法时间复杂度

小问题: 下面哪个循环的时间复杂度是使用的排序算法算法的时间复杂度?
A: 用于输入数组的循环
B: 用于排序的循环

答案: B

为什么用于排序的循环的时间复杂度才是排序算法的时间复杂度? 假设说你在做数学题, 所有的数据你一定可以全部\(get\), 直接玩出结果, 这个玩出结果的时间就是你做题的时间, 你读题的时间是你读题的时间, 而不是你做题的时间, 回到问题, 输入数据的时间复杂度是输入数据的时间复杂度, 排序的时间复杂度是排序的时间复杂度, 所以排序的时间复杂度是用于排序的循环的复杂度.

所以我们可以知道, 算法的时间复杂度就是运行算法的代码块的时间复杂度, 计算这个代码块的复杂度即可知道程序使用的算法的时间复杂度.