算法符号的含义是什么 [英] What is meaning of Algorithmic Notations

问题描述

作为大O表示法，它显示了最坏情况的可能性.

Theta表示法是什么，Theta表示法，Little-O表示法，Little Omega表示法是什么.

如果可能的话，请用简单的英语而不是数学来提问.

Hi,

As Big O notation, its shows worst case possibility.

What Theta Notation like, Theta Notation,Little-O Notation ,Little Omega Notation means.

If possible please give question in simple English rather that Mathematics.

Thanks

推荐答案

您不能真正用简单英语"来定义这些符号-它们是复杂的数学概念，需要精确的定义才能显示出明显的区别.

Google:看看Wiki和Wolfram Alpha，它们都可以解释它们，但不是用简单的英语！

You can''t really define these notations in "simple English" - they are complicated mathematical concepts which need precise definitions to show the significant differences.

Google: Look at Wiki, and a Wolfram Alpha - they both explain them, but not in simple English!

简单的英语答案:"拿一本数学书并对其进行研究"(或其他更权威的词:"没有通往几何学的皇家之路").

Simple English Answer: "Get a Math book and study it" (or, with other, more authoritative words: "There is no Royal Road to geometry").

首先请注意，Big O并非专门针对与算法的最坏情况行为有关，但与任何函数的所谓渐近行为有关，即当N变为无穷大时，该函数如何与极限值中的另一个函数进行比较.

f(N)= O(g(N))意味着f增长得像g或更快.

f(N)=大写omega(g(N))表示f像g或更慢地增长.

f(N)=小写theta(g(N))表示f像g一样增长.

f(N)= o(g(N))表示f/g为零.

f(N)=小写omega(g(N))表示f/g达到无穷大.

示例:N个前整数的总和为小写theta(N ^ 2);对N个数字进行排序肯定会花费时间O(N)，因为您需要至少一次查看每个数字； N.log(N)是大写的omega(N.sqrt(N))...

此表示法可以应用于算法的最坏情况/最佳情况/平均情况运行时间，也可以应用于算法的已知上限/下限.

First note that Big O is not specifically related to the worst-case behavior of an algorithm, but to the so called asymptotic behavior of any function, i.e. how the function compares to another one in the limit when N goes to infinity.

f(N) = O(g(N)) means that f grows like g or faster.

f(N) = uppercase omega(g(N)) means that f grows like g or slower.

f(N) = lowercase theta(g(N)) means that f grows like g.

f(N) = o(g(N)) means that f / g goes to zero.

f(N) = lowercase omega(g(N)) means that f / g goes to infinity.

Example: the sum of the N first integers is lowercase theta(N^2); sorting N numbers certainly takes time O(N) because you need to look at every number at least once; N.log(N) is uppercase omega(N.sqrt(N))...

This notation can apply to the worst-case/best-case/average-case running time of algorithms, or to known upper/lower bounds of these.

这篇关于算法符号的含义是什么的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！