英文:
What is the runtime complexity of isPrime(n) if you iterate up to sqrt(n)
问题
以下是已翻译的部分：
What would the Big O for the following method?
boolean isPrime( num )
i = 2
while i <= sqrt(num)
if num % i == 0
return false
i += 1
return true
My thought is `O(sqrt(n))`, which isn't a typical answer.
Below are a couple of tables to clarify my reasoning:
In this table, every time N is quadrupled, the number of iterations only doubles:
| N | iterations = sqrt(N) |
|------|----------------------|
| 4 | 2 |
| 16 | 4 |
| 64 | 8 |
| 256 | 16 |
| 1024 | 32 |
To contrast this behavior with a linear function,
if we looped **while i <= num/2** instead, the table would be:
| N | iterations = N/2 |
|------|-------------------|
| 4 | 2 |
| 16 | 8 |
| 64 | 32 |
| 256 | 128 |
| 1024 | 512 |
Now every time N is quadrupled, the number of iterations also quadruples.
I.e. the runtime varies directly with N.
英文:
What would the Big O for the following method?
boolean isPrime( num )
i = 2
while i <= sqrt(num)
if num % i == 0
return false
i += 1
return true
My thought is O(sqrt(n)), which isn't a typical answer.
Below are a couple of tables to clarify my reasoning:
In this table, every time N is quadrupled, the number of iterations only doubles.
| N | iterations = sqrt(N) |
|---|---|
| 4 | 2 |
| 16 | 4 |
| 64 | 8 |
| 256 | 16 |
| 1024 | 32 |
To contrast this behavior with a linear function,
if we looped while i <= num/2 instead, the table would be:
| N | iterations = N/2 |
|---|---|
| 4 | 2 |
| 16 | 8 |
| 64 | 32 |
| 256 | 128 |
| 1024 | 512 |
Now every time N is quadrupled, the number of iterations also quadruples.
I.e. the runtime varies directly with N.
答案1
得分: 2
你是对的 - 检查到√n会给你更好的复杂性。如果你定义num = n并假设取模运算是常数时间，那么你的时间复杂度是正确的。
这不是一个'典型答案'，正如你所说，通常我们根据输入的大小来衡量时间复杂度。要将num编码为二进制，我们需要log2(num)位（以及其他任何非平凡的基数也是如此），所以实际输入大小为n = log2(num)。
如果我们以这种方式定义n，那么你会发现num = O(2n)，因此你的总时间复杂度变为O(√(2n))或O(20.5n)。
然而，这并不比你的表达更正确，只是一种更常见（也更有用）的表达方式，它可能会澄清为什么当你搜索时你的答案看起来不典型。
最终重要的是你定义了你的n。如果你没有定义，读者可能会假定它是num的对数，他们可能会认为你错误地声称你的算法是世界上最快的。
英文:
You are right - checking up to √n gives you a much better complexity. And if you define num = n and assume the modulo operator is constant time, then your time complexity is correct.
The reason this is not a 'typical answer', as you state, is that typically we measure time complexity on the size of the input. To encode num in binary, we need log<sub>2</sub>(num) bits (and similarly with any other nontrivial base) so the actual input size is n = log<sub>2</sub>(num).
If we define n this way, then you will find that num = O(2<sup>n</sup>), so your overall time complexity becomes O(√(2<sup>n</sup>)) or O(2<sup>0.5n</sup>).
However, this is not more correct than your expression, it is just a more common (and more useful) way to express it, and it might clarify why your answer doesn't seem typical when you search.
Ultimately what matters is that you define your n. If you don't, it is probably assumed by the reader that it's the logarithm of num and they might think you falsely claim your algorithm is the fastest in the world.
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论