bigonotation.html

来自「数据结构词典（英文）」· HTML 代码 · 共 48 行

HTML
48 行
字号 
<!DOCTYPE HTML PUBLIC "-//IETF//DTD W3 HTML 2.0//EN">
<HTML lang="en-US">
<HEAD>
<TITLE>big-O notation</TITLE>
<META name="description"
  content="Definition of big-O notation,
	possibly with links to more information and implementations.">
<META name="keywords" content="big-O notation">
</HEAD>
<BODY BGCOLOR="#FFFFFF">

<H1>big-O notation</H1>
<P>
(definition)

<P>
<strong>Definition:</strong>
A theoretical measure of the execution of an <a href="algorithm.html" tppabs="http://hissa.nist.gov/dads/HTML/algorithm.html"><em>algorithm</em></a>, usually the time or memory needed, given the problem size n, which is usually the number of items.  Informally, saying some equation f(n) = O(g(n)) means it is less than some constant multiple of g(n).  More formally it means there are positive constants c and k, such that  0  <img src="leq.gif" tppabs="http://hissa.nist.gov/dads/HTML/Images/leq.gif" border=0 height=7  width=14 alt="less than or equal to"> f(n)  <img src="leq.gif" tppabs="http://hissa.nist.gov/dads/HTML/Images/leq.gif" border=0 height=7  width=14 alt="less than or equal to"> cg(n) for all n  <img src="geq.gif" tppabs="http://hissa.nist.gov/dads/HTML/Images/geq.gif" border=0 height=7  width=14 alt="greater than or equal to"> k. The values of c and k must be fixed for the function f and must not depend on n.
<P><strong>See also</strong>
<a href="omegaCapital.html" tppabs="http://hissa.nist.gov/dads/HTML/omegaCapital.html"><em> <img src="Omega-1.gif" tppabs="http://hissa.nist.gov/dads/HTML/Images/Omega.gif"  border=0 height=10 width=9  alt="Capital Omega">(n)</em></a>, <a href="omega.html" tppabs="http://hissa.nist.gov/dads/HTML/omega.html"><em> <img src="omega-1.gif" tppabs="http://hissa.nist.gov/dads/HTML/Images/omega.gif"  border=0 height=7  width=9  alt="omega">(n)</em></a>, <a href="theta.html" tppabs="http://hissa.nist.gov/dads/HTML/theta.html"><em> <img src="Theta-1.gif" tppabs="http://hissa.nist.gov/dads/HTML/Images/Theta.gif"  border=0 height=10 width=8  alt="Capital Theta">(n)</em></a>, <a href="littleOnottn.html" tppabs="http://hissa.nist.gov/dads/HTML/littleOnottn.html"><em>little-o notation</em></a>, <a href="asympupprbnd.html" tppabs="http://hissa.nist.gov/dads/HTML/asympupprbnd.html"><em>asymptotic upper bound</em></a>, <a href="np.html" tppabs="http://hissa.nist.gov/dads/HTML/np.html"><em>NP</em></a>.
<P><em>Note:
As an example, n<sup>2</sup> + 3n + 4 is O(n<sup>2</sup>), since n<sup>2</sup> + 3n + 4 &lt; 2n<sup>2</sup> for all n &gt; 10.  Strictly speaking, 3n + 4 is O(n<sup>2</sup>), too, but big-O notation is often misused to mean equal to rather than less than. The notion of equal to is expressed by <a href="theta.html" tppabs="http://hissa.nist.gov/dads/HTML/theta.html"><em> <img src="Theta-1.gif" tppabs="http://hissa.nist.gov/dads/HTML/Images/Theta.gif"  border=0 height=10 width=8  alt="Capital Theta">(n)</em></a>. <P> The importance of this measure can be seen in trying to decide whether an algorithm is adequate, but may just need a better implementation, or the algorithm will always be too slow on a big enough input.  For instance, <a href="quicksort.html" tppabs="http://hissa.nist.gov/dads/HTML/quicksort.html"><em>quicksort</em></a>, which is O(n log n) on average, running on a small desktop computer can beat <a href="bubblesort.html" tppabs="http://hissa.nist.gov/dads/HTML/bubblesort.html"><em>bubble sort</em></a>, which is O(n<sup>2</sup>), running on a supercomputer if there are a lot of numbers to sort.  To sort 1,000,000 numbers, the quicksort takes 6,000,000 steps on average, while the bubble sort takes 1,000,000,000,000 steps! <P> Strictly, the character is the upper case Greek letter omicron, not the letter O.</em>
<P>Author: <a href="terms.html#authorPEB" tppabs="http://hissa.nist.gov/dads/terms.html#authorPEB">PEB</a>

<hr>

Go to the
<A HREF="terms.html" tppabs="http://hissa.nist.gov/dads/terms.html">Algorithms, Data Structures, and Problems</A>
home page.

<hr>

If you have suggestions, corrections, or comments, please get in touch
with
<a href="javascript:if(confirm('http://hissa.nist.gov/~black/black.html  \n\nThis file was not retrieved by Teleport Pro, because it is addressed on a domain or path outside the boundaries set for its Starting Address.  \n\nDo you want to open it from the server?'))window.location='http://hissa.nist.gov/~black/black.html'" tppabs="http://hissa.nist.gov/~black/black.html">Paul E. Black</a>
&nbsp;(<a href="mailto:paul.black@nist.gov">paul.black@nist.gov</a>).

<p>
Entry modified Fri Jan  7 09:57:14 2000.<BR>
HTML page formatted Mon Jan 10 09:20:53 2000.

<P>
This page's URL is
<A href="bigOnotation.html" tppabs="http://hissa.nist.gov/dads/HTML/bigOnotation.html">http://hissa.nist.gov/dads/HTML/bigOnotation.html</A>

</BODY>
</HTML>

bigonotation.html - 源码说明

本页面展示了「数据结构词典（英文）」中的 bigonotation.html 源码文件，采用 HTML 编程语言编写，共 48 行代码。您可以在线阅读完整代码内容，也可以返回资源详情页下载完整源码包进行本地学习和开发。

虫虫下载站收录了大量与数据结构相关的技术资源，包括源代码、技术文档、电路图等，是电子工程师和嵌入式开发者的专业学习平台。

⌨️ 快捷键说明

复制代码Ctrl + C
搜索代码Ctrl + F
全屏模式F11
增大字号Ctrl + =
减小字号Ctrl + -
显示快捷键?