算法大o

Ⅰ 算法中描述复杂度的大O是什么意思

在“计算机算法复杂性分析”课程中，通常使用大 O 符号表述时间复杂度。常见的有：（1）、O(n²)：表示当 n 呈线性增长时，计算量按 n² 规律增大。该种算法是效率最低的一种。
（2）、再例如：要在一个大小为 n 的整数数组中，找到一个该数组里面的最大的一个整数，因此你需要把 n 个整数都扫描一遍，操作次数为 n，那么该时间复杂度就是O(n)。

Ⅱ 算法基础之大O表示法

    大O表示法是一种特殊的表示法，其用来 指出算法的速度有多块

    注意：大O表示法指出了最糟糕情况下的运行时间

    1：对于普通的简单查找算法，如果有100个元素，最多需要猜测100次，如果有40亿个元素，最多需要40亿次，即最多需要猜测的次数与元素的个数成正比，被称为 线性时间 ，即：O(n)

    2：对于二分查找算法，100个元素最多需要猜测7次，而40亿的元素也仅仅最多需猜测32次，其运行时间为 对数时间 ，即：O(logN)

    下面做一个算法执行时间增速的实验：

    采用简单的查找算法，我们知道，随着所需要查找元素个数的递增，所需要的时间也是呈线性递增的。

    而对于二分查找，其随着查找元素的递增，所需要的查找时间的增速是很缓慢的。（ 摘自算法简介 ）

大O表示法指出了算法有多块，其并没有单位，即并非是指以秒为单位的，大O表示法让你能够比较操作数，用来指出算法运行时间的增速。

    简单查询算法用大O表示法：O(N)

    二分查找算法用大O表示法：O(logN)

    N表示的是操作数

    综上所述，我们知道了算法的速度指的并非时间，而是操作数的增速。在谈论算法的速度时，我们说的是随着输入数的增加，其运行时间将会以什么样的速度增加。

    在计算机领域中有一个非常着名的旅行商的问题，其计算时间增加的非常快。

    简介：有一位旅行商，需要前往5个城市，同时要保证旅程最短，故可考虑前往这些城市的所有可能顺序，对于每一种顺序，都计算出总旅程，再挑选出旅程最短的路线，5个城市就会有120种不同的排列方式。即5个城市需要120次操作，涉及6个城市时，需要720次操作，7个城市时，需要5040次操作。

    综上涉及到n个城市时，需要执行n!（n的阶乘）次操作才能计算出最终需要的最短旅程路线。用大O表示法为O(N!)，即 阶乘时间。

如果涉及的城市数量过多，会造成计算出结果时，太阳已经下山了...

Ⅲ 算法分析中O（n）什么含义

O(n)这个大O表示的是最坏情况下的时间复杂度，就比如你举的例子，一共n^3次乘法和n^3次加法，那么加起来就是2×n^3。 然后如果有一个表达式f(n)，使得n趋于无穷大的时候，lim(2×n^3)/f(n)=常数c，那么就可以用大O表示。表示为O(f(n))，而且规定f(n)的表达式是不带常数的系数的，那么在这里f(n)=n^3。 一般用大O表示算法复杂度只需要取次数最高的项，而且去掉系数就OK了，不用每次都这么算的。三重循环而且每重循环都执行n次的话直接O(n^3)就好了。

Ⅳ 大O表示法

表示时间的大O符号，是用来描述算法效率的语言和度量单位。
大O表示法分析了算法的运行时间如何随列表的增长而增长，指出了算法最糟情况下的运行时间。

n为列表的长度，（n）作为大O表示法的操作数。

大O表示法通常不考虑常量，因为如果这两种算法的大O运行时间不同，这个常量将无关要紧。
大O表示法不考虑乘以、除以、加上或减去的数字。如O(n+26)、O(n-26)、O(n*26)、O(n/26)，它们都应该表示为O(n)。

如下图：

其中Ο(log2n )、Ο(n)、 Ο(nlog2n )、Ο(n2)和Ο(n3)称为多项式时间，而Ο( 2n)和Ο(n!)称为指数时间。计算机科学家普遍认为前者（即多项式时间复杂度的算法）是有效算法，把这类问题称为P（Polynomial,多项式）类问题，而把后者（即指数时间复杂度的算法）称为NP（Non-Deterministic Polynomial,非确定多项式）问题。

1、《算法图解》 https://www.manning.com/books/grokking-algorithms
2、《算法的基本概念》 https://www.zybuluo.com/defias/note/286416