时间复杂度(Time Complexity)

一、简介

        时间复杂度，又叫时间复杂性，也就是我们常说的大O。时间复杂度是不容忽视的衡量算法好坏的重要指标。

        时间复杂度是一个函数，用于描述该算法的运行时间。

        举个简单的例子：一个20米的木头，一群蚂蚁三年吃一米，那吃掉整个木头要多少年？答案是20*3=60年。那木头是N米呢？那就需要3N年。如果这是一个函数，就可以记作T(N)=3N。

        时间复杂度就是把T(N)化简为一个可以是N，,等等的数量级。

        那如何推导时间复杂度呢？

如果运行时间是常数量级，用常数1表示。

只保留时间函数中的最高阶项。

如果最高阶项存在，则省去最高阶项前面的系数。

        那我们再看看刚才的例子：最高阶段为3N，省去系数3，转化的时间复杂度为O(N)。

        数字16不断地除以2，除几次以后的结果等于1？这里要涉及到数学当中的对数，以2位底，16的对数，可以简写为log16。也就需要 5*log16=5*4=20 天。

        如果是N呢？

        需要5X*ogn=5logn天，记作 T(n)=5logn。省去系数5，得到时间复杂度为O(logn)。

        那T(2)怎么转化时间复杂度呢？很简单，由于只有常数量级，所以直接转化为O(1)。

常见的时间复杂度有：
常数阶O(1)；
对数阶O(log2 n)；
线性阶O(n)；
线性对数阶O(n log2 n)；
平⽅阶O(n^2)；
⽴⽅阶O(n^3)；
k次⽅阶O(n^K)；
指数阶O(2^n)。

---

以上就是本文的全部内容啦！感谢阅读！