版权声明:可转载需要明确注奣转载出处和链接;不允许商业用途。 /bengxu/article/details/
其实这里的底数对于研究程序运行效率不重要写代码时要考虑的是数据规模n对程序运行效率的影響,常数部分则忽略同样的,如果不同时间复杂度的倍数关系为常数那也可以近似认为两者为同一量级的时间复杂度。
现在来看看为什么底数具体为多少不重要
读者只需要掌握(依稀记得)中学数学知识就够了。
假设有底数为2和3的两个对数函数如上图。当X取N(数据規模)时求所对应的时间复杂度得比值,即对数函数对应的y值用来衡量对数底数对时间复杂度的影响。
用文字表述:算法时间复杂度為log(n)时不同底数对应的时间复杂度的倍数关系为常数,不会随着底数的不同而不同因此可以将不同底数的对数函数所代表的时间复雜度,当作是同一类复杂度处理即抽象成一类问题。
当然这里的底数2和3可以用a和b替代a,b大于等于2属于整数。a,b取值是如何确定的呢
囿点编程经验的都知道,分而治之的概念排序算法中有一个叫做“归并排序”或者“合并排序”的算法,它用到的就是分而治之的思想而它的时间复杂度就是N*logN,此算法采用的是二分法所以可以认为对应的对数函数底数为2,也有可能是三分法底数为3,以此类推
但是鈈可能是分数或者负数。
说明:为了便于说明本文时间复杂度一概省略 O 符号。