时间复杂度:根号n一般来说大于log(n)
原创
已于 2024-06-11 15:02:40 修改
·
5.1k 阅读
·
2
·
2
·
CC 4.0 BY-SA版权
版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
文章标签：
#算法
#c++
#时间复杂度
于 2023-05-15 00:28:56 首次发布
文章探讨了函数f(x)=√x-log_2x的导数，确定了其单调性的变化，指出函数在x=(ln2)^2/4处从减变增。图像显示函数与y=log_2x的交点在x=4和x=16。当x>16时，√x总是大于log_2x，强调了√x的优势。
f
(
x
)
=
x
−
l
o
g
2
x
f(x)=\sqrt{x}-log_2 x
f(x)=x
−log2x 对这函数求导后，比较分母大小，可以得到结论
f
(
x
)
f(x)
f(x)先减后增，分界点为
x
=
4
(
l
n
2
)
2
x = \frac{4}{(ln2)^2}
x=(ln2)24
f
(
x
)
f(x)
f(x)的图像如下所示：
![在这里插入图片描述](https://img-blog.csdnimg.cn/4967018e954341298bdf20b59524f236.png 两个函数的图像如下，只在
x
=
4
,
16
x = 4,16
x=4,16时有交点
当n>16时，就必然
x
>
l
o
g
2
x
\sqrt{x}>log_2 x
x
>log2x，故一般来说，
l
o
g
2
x
log_2 x
log2x更优 灵神题解的优越性，灵神题解
典例 2： 题目中灵神题解为nlogn解法，通过以下的分块解法为n
n
\sqrt{n}
n
，可以明显发现差距——n
n
\sqrt{n}
n
要慢很多。