算法的时间复杂度
大小为 n=100 的算法需要 21 秒运行。当大小 n=1000 时，运行需要 31 秒；当 n=10000 时，运行需要 41 秒。运行复杂度是多少？
如果我尝试 O(n) 那么： T(n)=(21*1000)/100 = 210 秒（不是 O(n)）
如果我尝试 O(n^2) 那么： T(n)=(21*1000^2)/100^2 = 2100 s （不是 O(n^2)）
如果我尝试 O(log n) 那么： T(n)=(21*log1000)/log100=31.5 （不是 O(log n)）
我给出的另一个选项是 O(1/n)。我该如何计算这个？
An algorith with size n=100 takes 21 seconds to run. With size n=1000 it takes 31 seconds and with n=10000 takes 41 seconds to run. What is the running complexity?
If I try O(n) Then: T(n)=(21*1000)/100 = 210 s (Not O(n))
If I try O(n^2) Then: T(n)=(21*1000^2)/100^2 = 2100 s (Not O(n^2))
If I try O(log n) then: T(n)=(21*log1000)/log100=31.5 (Not O(log n))
The other option I am given is O(1/n). How do I calculate this?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
看起来像
O(lgn)。当对数的底数为 10 时，
n的时间为T(n) = 10*log(n) + 1。looks like an
O(lgn).The time for
nisT(n) = 10*log(n) + 1when the base of the log is 10.要解决这个问题，首先要绘制各个类的一些函数。例如，要了解
O(n)线性类绘制函数T(n)=n并了解O(n^2)< /code> 类绘制函数T(n)=n^2。这将帮助您识别各种函数的形状。之后，用 x 轴上的 n 值和 y 轴上的时间值绘制问题中给出的点。你应该能够很快认出这道题的形状。
提示：这不是
O(log n):-)To solve this problem start by plotting some functions from the various classes. For example to learn about the
O(n)linear class plot the functionT(n)=nand to learn about theO(n^2)class plot the functionT(n)=n^2. This will help you recognize the shape of the various functions.After that, plot the points given in your questions with the values of n in the x-axis and the timed values on the y-axis. You should be able to quickly recognize the shape in this question.
Hint: It's not
O(log n):-)