VB.net 2010 视频教程 VB.net 2010 视频教程 python基础视频教程
SQL Server 2008 视频教程 c#入门经典教程 Visual Basic从门到精通视频教程
当前位置:
首页 > C#教程 >
  • 算法-1 算法复杂度

一 算法复杂度

算法复杂度分为时间复杂度和空间复杂度。时间复杂度是指执行算法所需要的计算工作量;而空间复杂度是指执行这个算法所需要的内存空间。

算法的复杂性体运行该算法时的计算机所需资源的多少,计算机资源最重要的是时间和空间(即寄存器)资源,因此复杂度分为时间和空间复杂度。

 

二 时间复杂度

2.1 关于时间复杂度

一个算法花费的时间与算法中语句的执行次数成正比例,算法中语句执行次数越多,它花费时间就越多。一个算法中的语句执行次数称为语句时间频度。记为T(n)。

 

假设算法的问题规模为n,算法中操作单元的数量用函数 f(n) 来表示,当n趋近于无穷大时,T(n) / f(n) 的极限值为不等于零的常数,

即随着数据规模n的增大,算法执行时间的增长率和 f(n)  的增长率相同,则称f(n)是T(n)的同数量级函数。记作T(n)=O(f(n))。

则称O(f(n)) 为算法的渐进时间复杂度,简称时间复杂度(Time complexity)。

 

时间复杂度用大O符号(big O)表述,不包括f(n)函数的低阶项和首项系数。

不同的数据规模n可能造成算法的运行时间不同,因此通常使用算法的最坏情况来估计时间复杂度。

2.2 常数操作

常数时间的操作:一个操作如果和样本的数据量没有关系,每次都是固定时间内完成操作,叫做常数操作。

常数时间的操作是指算法代码中的指令都是固定时间的操作,指令是和数据量没有关系,比如加、减、乘、除、模、位运算,或数组的寻址。

2.3 常数时间

若对于一个算法,T(n)的上界与输入n的大小无关,则称其具有常数时间,记作O(1)时间。例如访问数组中的单个元素,是常数因为访问它只需要一条指令。

但是,找到无序数组中的最小元素则不是,因为这需要遍历所有元素来找出最小值。这是一项线性时间的操作,也称O(n)时间。

int i = 1;
int j = 2;
i = j++;
j = j << 2;
int m = (i + j) / 2;

2.4 线性时间

如果一个算法的时间复杂度为O(n),则称这个算法具有线性时间,或O(n)时间。这意味着对于足够大的输入,运行时间增加的大小与输入成线性关系。

例如,一个计算列表所有元素的和的程序,需要的时间与列表的长度成正比。

for (int i = 1; i <= n; ++i)
{
    int j = i;
}

2.5 对数时间

若算法的T(n) = O(log n),则称其具有对数时间。由于计算机使用二进制的记数系统,未写明底数时,默认以2为底。

常见的具有对数时间的算法有二叉树的相关操作和二分查找。

对数时间的算法是非常有效的,因为每增加一个输入,其所需要的额外计算时间会变小。

int i = 1;
while (i < n)
{
    i = i * 2;
}

2.6 线性对数时间

若算法时间复杂度T(n) = O(nlog n),则称这个算法具有线性对数时间。线性对数时间增长得比线性时间要快,但是对于任何含有n,且n的幂指数大于1的多项式时间来说,线性对数时间增长得慢。

例如方法Method1

复制代码
void Method1(int n)
{
    for (int i = 0; i < n; i++)
    {
        Method2(n);
    }
}

void Method2(int n)
{
    for (int j = 1; j <= n; j = j * 2)
    {
        Console.WriteLine(j);
    }
}
复制代码

 

二 空间复杂度

空间复杂度(Space Complexity):是对一个算法在运行过程中临时占用存储空间大小的量度,记做S(n)=O(f(n))。

比如插入的时间复杂度是O(n^2),空间复杂度是O(1) 。而一般的递归算法的空间复杂度为O(n),因为每次递归都要存储返回信息。

例,空间复杂度O(1)

int i = 1;
int j = 2;
i = j++;
j = j << 2;
int m = (i + j) / 2;

空间复杂度O(n)

复制代码
int[] m = new int[n];
int j = 0;
for (i = 1; i <= n; ++i)
{
    j = i;
    j++;
}
复制代码

 

以上。

出处:https://www.cnblogs.com/wwwen/p/16902006.html


相关教程