查找公式的大 O 符号
Finding big-O notation of forumulas
我想看看我在寻找某些公式的大 O 符号方面的工作是否正确。这些公式中的每一个都是某种算法中的操作数。这些是公式：
论坛
a.) n2 + 5n
b.) 3n2 + 5n
c.) (n + 7)(n - 2)
d.) 100n + 5
e.) 5n +3n2
f.) 2n的位数
g.)n在低于1.0之前可以除以10的次数
我的答案：
a.) O(n2)
b.) O(n2)
c.) O(n2)
d.) O(n)
e.) O(n2)
f.) O(n)
g.) O(n)
我的分析是否正确？
让我们一次过一遍。
a.) n2 + 5. Your answer: O(n2)
是的！您正确地忽略了低阶项。
b.) 3n2 + 5n. Your answer: O(n2).
是的！ Big-O 午餐吃常数因子。
c.) (n + 7)(n - 2). Your answer: O(n2).
是的！您可以将其扩展为 n2 + 5n - 14 并从那里删除低阶项以获得 O(n2)，或者你可以意识到 n + 7 = O(n) 和 n - 2 = O(n) 可以看出这是两个项的乘积，每个项都是 O(n)。
d.) 100n + 5. Your answer: O(n).
是的！同样，删除常量和低阶项。
e.) 5n + 3n2. Your answer: O(n2).
是的！顺序无关紧要； 5n 仍然是低阶项。
f.) The number of digits in 2n. Your answer: O(n).
这个在技术上是正确的，但不是很好的绑定。请记住，大 O 表示法给出了一个上限，您认为数字 n 有 O(n) 位是正确的，但只是在 n 的位数渐近小于 n 的意义上。要了解为什么这个界限不是很好，让我们看一下数字 10、100、1000、10000 和 100000。这些数字分别有 2、3、4、5 和 6 位数字。换句话说，增加十倍只会使位数增加一位。如果你的 O(n) 界限很紧，那么你会期望每次将数字增加十倍时数字的数量都会增加十倍，这是不准确的。
作为这个提示，如果一个数字有 d 位，那么它在 10d 和 10d+1 之间 - 1. 这意味着 d 位数字的数值是 d 的指数函数。因此，如果您从 位数 开始，则 数值 呈指数级增长。向后尝试 运行。如果您知道 数值 比 位数 的数量呈指数增长，那么作为函数的位数意味着什么的数值？
f.) The number of times that n can be divided by 10 before dropping below 1.0. Your answer: O(n)
这个在技术上也是正确的，但不是很好的绑定。让我们以数字 100,000 为例。在低于 1.0 之前，您可以将其除以 10 七次，但是给出 O(n) 的界限意味着您是说答案作为 n 的函数线性增长，因此将 n 加倍应该使您可以加倍的次数除以十...但实际上是这样吗？
提示一下，一个数在低于 1.0 之前可以除以 10 的次数与该数的位数密切相关。如果你能解决这个问题，你就会解决（e）部分，反之亦然。
祝你好运！
我想看看我在寻找某些公式的大 O 符号方面的工作是否正确。这些公式中的每一个都是某种算法中的操作数。这些是公式：
论坛
a.) n2 + 5n
b.) 3n2 + 5n
c.) (n + 7)(n - 2)
d.) 100n + 5
e.) 5n +3n2
f.) 2n的位数
g.)n在低于1.0之前可以除以10的次数
我的答案：
a.) O(n2)
b.) O(n2)
c.) O(n2)
d.) O(n)
e.) O(n2)
f.) O(n)
g.) O(n)
我的分析是否正确？
让我们一次过一遍。
a.) n2 + 5. Your answer: O(n2)
是的！您正确地忽略了低阶项。
b.) 3n2 + 5n. Your answer: O(n2).
是的！ Big-O 午餐吃常数因子。
c.) (n + 7)(n - 2). Your answer: O(n2).
是的！您可以将其扩展为 n2 + 5n - 14 并从那里删除低阶项以获得 O(n2)，或者你可以意识到 n + 7 = O(n) 和 n - 2 = O(n) 可以看出这是两个项的乘积，每个项都是 O(n)。
d.) 100n + 5. Your answer: O(n).
是的！同样，删除常量和低阶项。
e.) 5n + 3n2. Your answer: O(n2).
是的！顺序无关紧要； 5n 仍然是低阶项。
f.) The number of digits in 2n. Your answer: O(n).
这个在技术上是正确的，但不是很好的绑定。请记住，大 O 表示法给出了一个上限，您认为数字 n 有 O(n) 位是正确的，但只是在 n 的位数渐近小于 n 的意义上。要了解为什么这个界限不是很好，让我们看一下数字 10、100、1000、10000 和 100000。这些数字分别有 2、3、4、5 和 6 位数字。换句话说，增加十倍只会使位数增加一位。如果你的 O(n) 界限很紧，那么你会期望每次将数字增加十倍时数字的数量都会增加十倍，这是不准确的。
作为这个提示，如果一个数字有 d 位，那么它在 10d 和 10d+1 之间 - 1. 这意味着 d 位数字的数值是 d 的指数函数。因此，如果您从 位数 开始，则 数值 呈指数级增长。向后尝试 运行。如果您知道 数值 比 位数 的数量呈指数增长，那么作为函数的位数意味着什么的数值？
f.) The number of times that n can be divided by 10 before dropping below 1.0. Your answer: O(n)
这个在技术上也是正确的，但不是很好的绑定。让我们以数字 100,000 为例。在低于 1.0 之前，您可以将其除以 10 七次，但是给出 O(n) 的界限意味着您是说答案作为 n 的函数线性增长，因此将 n 加倍应该使您可以加倍的次数除以十...但实际上是这样吗？
提示一下，一个数在低于 1.0 之前可以除以 10 的次数与该数的位数密切相关。如果你能解决这个问题，你就会解决（e）部分，反之亦然。
祝你好运！