[数据结构与算法]时间复杂度

定义

时间复杂度是衡量一个代码好坏的基础：运行时间与占用空间。

输入规模和运行环境和运行次数是决定时间复杂度的因素。

如二分法查找0（logn）? 所执行次数为a*logn

找数组中最大/小值0（n） 所执行次数为 b*n

归并排序算法0(nlogn)? ? ?所执行次数为c*nlogn

思路如

　for (i=1; i<=n; i++)
　　       x++;
　　for (i=1; i<=n; i++)
　     　for (j=1; j<=n; j++)
　　          x++;

　第一个for循环的时间复杂度为Ο(n)，第二个for循环的时间复杂度为Ο(n2)，则整个算法的时间复杂度为Ο(n+n2)=Ο(n2)。

　　Ο(1)表示基本语句的执行次数是一个常数，一般来说，只要算法中不存在循环语句，其时间复杂度就是Ο(1)。其中Ο(log2n)、Ο(n)、 Ο(nlog2n)、Ο(n2)和Ο(n3)称为多项式时间，而Ο(2n)和Ο(n!)称为指数时间。