Big-O代数简化问题 [英] Big-O Algebra Simplification Issue

问题描述

我已经处理了几个小时的问题，需要澄清一下:

I've been working on a problem for several hours now, and I need clarification:

我需要(尽可能)简化以下big-O表达式.对于每一个，我写下了我认为是正确的答案.我想要解决方案，但是如果我不正确的话，也希望能得到一个解释.我正在尝试尽可能多地学习Big O表示法，并且我认为解决这些问题很有帮助.我只想确保自己走的路正确.

I needed to simplify (as much as possible) the following big-O expressions. For each, I put down what I thought was the correct answer. I would like solutions, but I would appreciate an explanation as well if I am incorrect. I am trying to learn Big O notation as well as possible, and I think doing these problems helped a lot. I just want to make sure I'm on the right path.

a)O(sqrt(n) + log(n)*log(n))

我认为这是O(n)

b)O(3log2 n + 2log3 n)

我认为这是O(log3 (n))

c)O(n^3 + 2n^2 +3n + 4)

我认为这是O(n^3)

感谢您的所有帮助！

推荐答案

让我们一次浏览一下.

O(sqrt(n)+ log(n)* log(n)).我以为这是 O(n)

您是正确的，这是O(n)，但这并不是一个特别严格的界限.让我们从一个简化的问题开始:O(sqrt(n))或O(log(n)* log(n))增长更快?使用该信息，您可以从求和中删除两个项之一吗?

You are correct that this is O(n), but that's not a particularly tight bound. Let's start with a simplifying question: which grows faster, O(sqrt(n)) or O(log(n) * log(n))? Using that information, can you drop one of the two terms from the summation?

O(3log2 n + 2log3 n).我以为这是 O(log3(n))

请记住，对于任何b和c，"big-O忽略对数的底"(即log _b n = O(log _c n)大于一).从技术上来说，您说的是O(log3 n)，但这不是最干净的解决方案.您最好在这里说O(log n).

Remember that "big-O ignores the base of logarithms" (that is, log_b n = O(log_c n) for any b and c that are greater than one). You're technically right that it's O(log3 n), but that's not the cleanest solution. You'd be better off saying O(log n) here.

O(n ^ 3 + 2n ^ 2 + 3n + 4).我以为这是 O(n ^ 3)

完全正确！之所以可行，是因为2n ² + 3n + 4为O(n ³ )，因此您可以从求和中删除这些项.现在，您可以使用类似的技巧简化对(a)部分的回答吗?

Exactly right! This works because 2n² + 3n + 4 is O(n³), so you can drop those terms from the summation. Now, can you use a similar trick to simplify your answer to part (a)?

希望这会有所帮助！

这篇关于Big-O代数简化问题的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！