Theta 符号的简单英语解释是什么?使用尽可能少的正式定义和简单的数学。
theta 表示法与大 O 表示法有何不同?谁能用通俗易懂的英语解释一下?
算法分析中有怎么用到的?我很困惑?
最佳答案
如果算法的运行时间是 Big Theta(f(n)),则它在 f(n) 的上下渐进界限。大 O 是一样的,只是边界只在上面。
直觉上,Big O(f(n)) 表示“我们可以确定,忽略常数因子和项,运行时间永远不会超过 f(n)。”粗略地说,如果您认为运行时“不好”,那么 Big O 就是最坏的情况。 Big Theta(f(n)) 表示“我们可以确定,忽略常数因子和项,运行时间总是随 f(n) 变化。”换句话说,Big Theta 是一个已知的紧界:它既是最坏的情况,也是最好的情况。
直觉的最后一次尝试:Big O 是“片面的”。 O(n) 运行时间也是 O(n^2) 和 O(2^n)。 Big Theta 并非如此。如果您的算法运行时间为 O(n),那么您已经证明它不是 Big Theta(n^2)。它可能是也可能不是 Big Theta(n)
一个例子是比较排序。信息论告诉我们排序至少需要 ceiling(n log n) 次比较,而我们实际上发明了 O(n log n) 算法(其中 n 是比较次数),所以排序比较是 Big Theta(n log n)。
关于algorithm - Theta 符号的简单英语解释?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/12332840/