算法的时间复杂度

算法

Posted by 朱坤乾 on August 15, 2020

T(n) = n

1:给小灰一条长10寸的面包,小灰每3天吃掉1寸,那么吃掉整个面包需要几天

答案自然是 3 X 10 = 30天。

如果面包的长度是 N 寸呢?

此时吃掉整个面包,需要 3 X n = 3n 天。

如果用一个函数来表达这个相对时间,可以记作 T(n) = 3n。

a^n = b(a>0,且a≠1),那么数n叫做bai以dua为底b的对数,记做n=log(a)b,

场景2:给小灰一条长16寸的面包,小灰每5天吃掉面包剩余长度的一半,第一次吃掉8寸,第二次吃掉4寸,第三次吃掉2寸……那么小灰把面包吃得只剩下1寸,需要多少天呢?

这个问题翻译一下,就是数字16不断地除以2,除几次以后的结果等于1?这里要涉及到数学当中的对数,以2位底,16的对数,可以简写为log16。

因此,把面包吃得只剩下1寸,需要 5 X log16 = 5 X 4 = 20 天。

如果面包的长度是 N 寸呢?

需要 5 X logn = 5logn天,记作 T(n) = 5logn。