如何决定表达算法的时间复杂度？
我们应该选择快递的时间复杂度方面O(n)还是theta(n)？因为函数f(n)可以表示为Big-Oh(g(n))或theta (g(n)).
我们什么时候选择大哦超过theta？
我已经解决了一个递归关系,其运行时间为Θ(2 ^ n),指数时间.如何找到相同的递归关系的Ω和O.
我猜如果它是Θ(2 ^ n),它也应该是O(2 ^ n),我是对的吗？我如何找到Ω,下限？
我尝试解决递归关系:
T(n)= 2T(n-1)+ C.
我在考试中得到了这个问题:命名一个既不是O(n)也不是Omega(n)的函数.
在尝试通过youtube自己学习这些东西后,我想这可能是一个正确的答案:
(n 3(1 + sin n))既不是O(n)也不是Omega(n).
那会准确吗？
我正在努力学习如何找到各种算法的大角度范围,但我很难理解如何做到这一点,即使在阅读了这里的一些问题以及有关该主题的讲座和教科书之后.所以举个例子
procedure for array a{
step=1
while(step <= n){
i = n
while(i >= step){
a[i]= a[i-step] + a[i]
i = i - 1}
step = step * 2}
}
我想弄清楚n在数组a中的索引数量方面的增加数量上的big-theta界限.我可以看到外部循环本身经历了log(n)次迭代,但我无法弄清楚如何表达内部循环中发生的事情.有没有人有解释或甚至可能尝试咨询的资源？
我的理解是,如果一个算法是O(1)它也是O(n),O(n^2),O(n^3)等这使得它显得有些苍白无力.例如,如果有人问我任何算法的Big-Oh表示法,我可以在O(n^n)不考虑它的情况下(字面意思)说,并且在大多数情况下在技术上是正确的.
既然(这是我的理解)这是真的,这有用的信息怎么样？使用类比,如果我问某人他们拥有多少房子,那么"1到无限"这样的答案就不是很有用.一个有用的答案(这有点像Big-Theta)将是"1".
我遇到了问题:
f(n) are asymptotically positive functions. Prove f(n) = ?(g(n)) iff g(n) = ?(f(n)).
我发现的一切都表明这个陈述是无效的.例如,我遇到的答案是:
f(n) = O(g(n)) implies g(n) = O(f(n))
f(n) = O(g(n)) means g(n) grows faster than f(n). It cannot imply that f(n) grows
faster than g(n). Hence not true.
另一个州:
If f(n) = O(g(n)) then O(f(n)). This is false. If f(n) = 1 and g(n) = n
for all natural numbers n, then f(n) <= g(n) for all natural numbers n, so
f(n) = O(g(n)). However, …试图理解Big O和嵌套循环我一直在阅读笔记,无法理解这个问题的嵌套循环部分是如何工作的......我有一个6 + 1.5n + nlogn的回答从讲座中写下但是不要不明白如何获得n log n部分
Simple Statement;
Simple Statement;
Simple Statement;
Simple Statement;
for ( int i = 0; i < ( n / 2 ); i++ ) {
Simple Statement;
Simple Statement;
Simple Statement;
}
Simple Statement;
Simple Statement;
for ( int i = 0; i < 2 * n; i++ ) {
for ( int j = 0; j < n; j = 2 * j ) {
Simple Statement;
Simple Statement;
}
}
我的理解是6是来自不在循环内的六个语句而1.5n来自3(n-1 …
这是真的？
f(n) = O(g(n)) === g(n) = Omega(f(n))
基本上它们可以互换，因为它们是对立的吗？
那么如果 F 在 G 的 Big O 中，那么 G 是 F 的 Big Omega？
它是 f(n)=theta(h(n)) 因为 theta 是可传递的。但是任何人都可以解释为什么 h(n)=theta(f(n))。