英文:
Difference between O(log n) and O(log n +1)
问题
我发现时间复杂度和空间复杂度非常令人困惑（如果有任何易于理解的博客/视频，请随时提供链接）。
在时间复杂度的情况下，+1是否有影响？或者O(log n)和O(log n + 1)被认为是相同的吗？
英文:
I find time and space complexity very confusing (if there are any easy to understand blogs/videos feel
free to link it).
Does the +1 there make a difference in case of time complexity? or is O(log n) considered the same as O(log n + 1)?
答案1
得分: 2
Additive and multiplicative constants never matter. For all constants M ≠ 0 and A, O(M ⋅ f(n) + A) = O(f(n)).
英文:
Additive and multiplicative constants never matter. For all constants M≠0 and A, O(M ⋅ f(n) + A) = O(f(n)).
答案2
得分: 0
在计算大O表示法时，常数实际上并不重要，因为我们在计算某物增长的速度，在这里的常数将会在大规模输入时完全无关紧要。
假设有两个排序算法，一个是O(n)，另一个是O(n^2)，给定输入n=50的情况下。
现在假设我们有一个O(n)的常数为500，另一个O(n^2)的常数为5：
O(n) = 50 * 500 = 25000
O(n^2) = 50 * 50 * 5 = 12500
在这种情况下，O(n^2)实际上更快。但是，假设我们有n=1,000,000的情况：
O(n) = 1,000,000 * 500 = 500,000,000
O(n^2) = 1,000,000 * 1,000,000 * 5 = 5,000,000,000,000
所以你可以看到，随着输入变得越来越大，差距会变得越来越大，因此在大O表示法的计算中，常数实际上并不重要。
英文:
When you are calculating the Big O notation, the Constants do not really matter, As we are calculating the speed at which something will grow, Having a constant here will be completely irrelevant with a large input.
Assuming having two algorithms for sorting with O(n) and O(n^2), given an input of n=50
Now assuming that we do have a constant for the O(n) of 500 and another constant for O(n^2) of 5
O(n) = 50 * 500 = 25000
O(n^2) = 50 * 50 * 5 = 12500
for this case, the O(n^2) is actually faster, But assuming we have n = 1,000,000 for example
O(n) = 1,000,000 * 500 = 500,000,000
O(n^2) = 1,000,000 * 1,000,000 * 5 = 5,000,000,000,000
So as you can see, as the input gets larger and larger the gap will grow, and therefore the constant does not really matter in the Big O notation calculations.
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论