刚学数据结构，关于时间复杂度有点不明白

比如  T(n)=nlog2n+5000n, 为啥时间复杂度是O(nlog2n)呢，是咋算的啊，是求T(n)的极限吗

14 个解决方案

#1

是选取上式中的高次部分，忽烈次要部分

#2

引用 1 楼 xingzhe2001 的回复:

是选取上式中的高次部分，忽烈次要部分

为什么啊。我记得在哪看到过，好像跟极限有点关系

#3

正式的做法是f(x)=O(g(x)) as x->a 当且仅当
[img=http://latex.codecogs.com/gif.latex?\lim_{x\rightarrow a}sup\left|\frac{f(x)}{g(x)}\right|<\infty][/img]
也就是在x大与某个值得时候有 f(x)<=M*|g(x)|
所以如果是低次的项，总可以找到个常数使得 小于 常数*高次，最后的结果及时保留最高次，忽略乘中常数。

#4

正式的做法是f(x)=O(g(x)) as x->a 当且仅当

也就是在x大与某个值得时候有 f(x)<=M*|g(x)|
所以如果是低次的项，总可以找到个常数使得 小于 常数*高次，最后的结果及时保留最高次，忽略乘中常数。

#5

引用 2 楼 asenpal 的回复:

引用 1 楼 xingzhe2001 的回复:
是选取上式中的高次部分，忽烈次要部分


为什么啊。我记得在哪看到过，好像跟极限有点关系

引用 1 楼 xingzhe2001 的回复:

是选取上式中的高次部分，忽烈次要部分

nlog2n+5000n 当 n ——> 无穷大 的时候 5000 相比 log2n 来说是可以忽略的

#6

有谁真懂的,就详细解释下!
拒绝不懂装懂哦

#7

复杂度是当输入趋向无穷大的时候带来的变化。


所以，忽略数量级小的。

T(n)=nlog2n+5000n

这个可以认为是nlogn
连2和5000n都可以忽略。

#8

看复杂度的时候都是忽略常数的
5000再大也不过是一个固定的常数，跟logn是没法比的
所以第一项在n足够大的时候“统治”了第二项

#9

画个二维数轴就知道了
当n趋向于无穷大的时候，整个函数的图像，趋向于没有低此项的函数图像

#10

引用 2 楼 asenpal 的回复:

引用 1 楼 xingzhe2001 的回复:
是选取上式中的高次部分，忽烈次要部分


为什么啊。我记得在哪看到过，好像跟极限有点关系

时间复杂度是语句频度n趋于无穷大时的同阶无穷大
即T(n)=nlog2n+5000n的同阶无穷大也就是O(nlog2n)

#11

的确如楼上所说

#12

时间复杂度是指程序代码段在处理问题规模(用n表示)的时候，所需要时间的度量计算方法。
计算复杂度：根据各项相对于规模变量n的函数项之和来判断的，哪个函数项对于问题n的函数
值的增量变化越大就是它了。其实计算增量的时候，可以用导数来计算。
T(n)=nlog2n+5000n可以看成是f1(n) = nlog2n 和 f2(n) = 5000n
的和：即T(n) = f1(n) + f2(n) (1)
明显的f2(n)的函数增长远没f1(n)的快。
所以时间复杂度应该是nlog2n
如果对函数进行求导出现同阶的情况那就的看无穷大的极限了。

#13

关于时间复杂度的计算有些是有规律可寻的。
对线性表的遍历的复杂度取决于线性表的元素个数即为n
读于树的遍历没有固定分析方法，指定对指定的树的类型和特点以及
算法本身来分析得到的。
对于多层嵌套代码的复杂度计算取决于循环层数以及循环量跟问题规模n的关系。

#14

当n到无穷的时候，就可以忽略了。