算法的时间复杂度是一个最糟糕的想法 [英] time complexity of algorithm that is a worst idea to draw a

问题描述

任何人都可以帮助我最坏情况下的时间复杂性，即以下算法的大喔我需要解决它我已经研究过但我无法提出最终解决方案。以下算法是将绘制一个圆圈任何关于这个算法的帮助或建议将是非常值得赞赏的


circle（radius）

for i = 10 to -10

，j = -10到10

d = sqrt（i + j）

如果半径-0.5< d<半径+ 0.5

puetpixel（i，j，1）

Can any one help me what will be the time complexity in worst case i.e Big Oh of the following algo I need to resolve it i have worked on it but am not able to come up with the final solution .the below algorithm is going to draw a circle any help or suggestion regarding this algo will be hidhly appreciatable

circle (radius)
for i =10 to -10
for j =-10 to 10
d = sqrt (i+j)
if radius -0.5 < d < radius + 0.5
puetpixel (i,j,1)

推荐答案

有两个循环，一个嵌套在另一个循环中。最外面的循环迭代n次

并且最里面的循环迭代m次，因此你采取O（n * m）步。如果m == n

那么你采取O（n ^ 2）步骤。


亲切的问候，


Jos

There are two loops, one nested in the other. The outermost loop iterates n times
and the innermost loop iterates m times so you take O(n*m) steps. If m == n
then you take O(n^2) steps.

kind regards,

Jos

你已经给出了整个算法的时间复杂度

谢谢


但是我不明白你的意思没有计算每个标准的时间复杂度，即


d = sqrt（i + j）

如果半径-0.5< d<半径+ 0.5

puetpixel（i，j，1）


您可以提供有关以下步骤的更多详细信息

首先计算每个标准的时间复杂度

然后加起来或乘以（取决于语句）每个语句的时间复杂度

这将给出我们的最终时间复杂度>


但是我无法理解的是每个参数的时间复杂程度



任何帮助或建议关于这个算法将是非常值得欣赏的

You have given The time complexity of the whole Algorithm
Thanks

But i dont understand that u have not calculated the timetime complexity of every statment i.e

d = sqrt (i+j)
if radius -0.5 < d < radius + 0.5
puetpixel (i,j,1)

Can u give more detail regarding following steps
First calculate the time complexity of each statment
Then add up or multiply (depending on the statment ) the time coplexity of each statment
Which will give our final Time complexity>

But i am not able to understand is that What will be the time complexity of each Statment


Any help or suggestion regarding this algo will be hidhly appreciatable

在分析算法的效率时，大O符号很有用。例如，完成大小为n的问题所花费的时间（或步数）可能是T（n）= 4n2 - 2n + 2.


As n变大，n2项将占主导地位，所以其他所有项都可以忽略不计？例如，当n = 500时，项4n2是2n项的1000倍。对大多数目的而言，忽略后者对表达式的价值可以忽略不计。


让我重复一遍......忽略2n项对计算时间的影响可以忽略不计当n接近无穷大时，需要完成算法，因此计算每个操作所花费的时间是无关紧要的，因为它们对函数的整体运行时间几乎没有影响。

Big O notation is useful when analyzing algorithms for efficiency. For example, the time (or the number of steps) it takes to complete a problem of size n might be found to be T(n) = 4n2 − 2n + 2.

As n grows large, the n2 term will come to dominate, so that all other terms can be neglected ? for instance when n = 500, the term 4n2 is 1000 times as large as the 2n term. Ignoring the latter would have negligible effect on the expression''s value for most purposes.

Let me repeat that... ignoring the 2n term will have negligible effect on calculating the time it takes to complete an algorithm as n approaches infinity, therefore calculating the time each operation takes is irrelevant since they have virtually no effect on the overall run time of your function.

这篇关于算法的时间复杂度是一个最糟糕的想法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！