如何找到任何算法的大 O/时间复杂度
所有，
我总是发现自己在寻找给定代码/算法的复杂性时持怀疑态度。前任。
FOR I=1 TO N
do J=1
WHILE J*J < I
do J=J+1
上面代码的时间复杂度为 Big Theta (N^(3/2)) 。但是，我不明白答案是如何得出的。
谁能指导我找到复杂性的步骤或任何可以帮助我的特定资源？大多数时候，我只找到复杂度为 N, lg N , N lg N 和 N^2 的代码
All,
I have always found myself being doubtful when it comes to finding the complexity of a given code/algorithm. Ex.
FOR I=1 TO N
do J=1
WHILE J*J < I
do J=J+1
The above code has time complexity of Big Theta (N^(3/2)) . However, I don't understand how the answer is derived.
Can anyone please guide me to the steps for finding the complexity or any specific resource that can help me? Most of the times, I only find code with complexity N, lg N , N lg N and N^2
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
方法始终相同：计算出作为 N 函数正在执行的操作数，然后丢弃低阶项和常量。
因此，在上面的示例中，内部循环迭代大约 sqrt(I) 次，因此我们有（大约）sqrt(1) + sqrt(2)< /em> + sqrt(3) + ... 结果是一个最高阶项为 N^(3/2) 的函数。
The approach is always the same: work out how many operations are being executed as a function of N, and then throw away low-order terms and constants.
So in your example above, the inner loop iterates approximately sqrt(I) times, so we have (approximately) sqrt(1) + sqrt(2) + sqrt(3) + ... The result is a function whose highest-order term is N^(3/2).