我如何检查大 O 的复杂性函数
How do i check the big O for complexity function
我有这个：
a) f(n) = n
b) f(n) = 1045n
c) f(n) = n2 + 70
d) f(n) = 7n + 3
e) f(n) = Cn + D (where C and D are both constants)
f) f(n) = 8
g) f(n) = n3 + n + 1
h) f(n) = 4n + 2log n + 5
我想看看它们的大O表示法是不是O(n)。
如何判断？
以及如何找到以下函数的大 O 表示法：
a) f(n) = 3n3 + n
b) f(n) = 3 log n + 5n
c) f(n) = 3n2 + 5n + 4
d) f(n) = 3n3 + n2 + 5n + 99
一般来说，函数的大O表示法是以出现的n的最大次方来衡量的。在您的情况下，这将是 n²，因为唯一的其他因素是 70，它是常数。
编辑：原始 post 仅包含函数 f(n) = n² + 70。
f(x) is O(g(x)) if there exists a constant c such that f(x) < c*g(x)
你应该看看你的函数中的 "biggest" 渐近因子（最高指数或类似的东西），那将是你的大 O
示例：f(n) = 2^n + n^5 + n^2 + n*log(n) + n
这个函数有 5 个影响大 O 的不同因素，从大到小排序，所以这个是 O(2^n)。删除 2^n，现在 f(n) 是 O(n^5)。
常数是 O(1)。
希望我解释得很好
参见this answer。
简而言之，没有固定的方法来确定 Big O 结果。严格来说，任何最终（对于某些 n）总是比你的函数更大的函数，都是它的大 O。在实践中，您正在寻找尽可能紧的界限。如果函数的唯一分量是 n 中的多项式，那么大 O 将只是出现的 n 的最大幂（或者更确切地说，n 的那个幂）。另一个需要知道的有用的事情是 log n 的阶数低于 n（但高于常量）。
我有这个：
a) f(n) = n
b) f(n) = 1045n
c) f(n) = n2 + 70
d) f(n) = 7n + 3
e) f(n) = Cn + D (where C and D are both constants)
f) f(n) = 8
g) f(n) = n3 + n + 1
h) f(n) = 4n + 2log n + 5
我想看看它们的大O表示法是不是O(n)。
如何判断？
以及如何找到以下函数的大 O 表示法：
a) f(n) = 3n3 + n
b) f(n) = 3 log n + 5n
c) f(n) = 3n2 + 5n + 4
d) f(n) = 3n3 + n2 + 5n + 99
一般来说，函数的大O表示法是以出现的n的最大次方来衡量的。在您的情况下，这将是 n²，因为唯一的其他因素是 70，它是常数。
编辑：原始 post 仅包含函数 f(n) = n² + 70。
f(x) is O(g(x)) if there exists a constant c such that f(x) < c*g(x)
你应该看看你的函数中的 "biggest" 渐近因子（最高指数或类似的东西），那将是你的大 O
示例：f(n) = 2^n + n^5 + n^2 + n*log(n) + n
这个函数有 5 个影响大 O 的不同因素，从大到小排序，所以这个是 O(2^n)。删除 2^n，现在 f(n) 是 O(n^5)。
常数是 O(1)。
希望我解释得很好
参见this answer。
简而言之，没有固定的方法来确定 Big O 结果。严格来说，任何最终（对于某些 n）总是比你的函数更大的函数，都是它的大 O。在实践中，您正在寻找尽可能紧的界限。如果函数的唯一分量是 n 中的多项式，那么大 O 将只是出现的 n 的最大幂（或者更确切地说，n 的那个幂）。另一个需要知道的有用的事情是 log n 的阶数低于 n（但高于常量）。