算法的时间代价

算法的时间代价

随便解释一下 ，解释的不好见谅
一个算法是解决某个问题的，比如n条数据排序问题，那么对于这个问题“n”就是它的问题规模
那么解决这个问题的算法的代价一定是n的函数，记为T(n)
为了比较不同算法之间的优劣，必须有一种方法将计算代价的函数进行变换，所以提出一种
概念叫做“复杂度”（好像是这么个意思,教材上的那个阴文单词背不出了)
记作T(n)=O(f(n)),表示代价T(n)和f(n)一样
比方说一个算法用时T(n)=n天 ，另一个算法用f(n)=100n天，可以证明
n=O(100n),那么就认为两个算法复杂度相同（1天和100天复杂度还相同,....)

搂住的后半句就是具体定义，“存在正常数C和N,当问题规模n>N时,有T(n)<=Cf(n)”意思就是说如果有一个正的常数C，和一个正的常数N，当n>N 不等式T(n)<=Cf(n)恒成立，就“称某算法的时间(或空间)代价T(n)=O(f(n))”

比如一个算法的代价是T(n)=100n ，那么当n>=1时，100n <= 101 n
那么就可以记作
T(n)=100n = O（n） 这里f(n)是f(n)=n，C=101，N=1

如以上回答内容为低俗、色情、不良、暴力、侵权、涉及违法等信息，可以点下面链接进行举报！

点此我要举报以上问答信息