时间复杂度的定义： （1）时间复杂度表示为O(f(n))，随问题规模n的逐渐增大，算法时间的增长率和f(n)相同 （2）O(1)：常数阶 （3）O(n)：线性阶 （4）O(\(n^2\))：平方介 （5）O(\(log_2n\))：对数阶c while(count < n){ //每次循环，count都会离n进一步，需要循环对数次 count = count*2; }
推到O阶的方法 （1）用常数1取代运行时的所有加法 （2）修改后的运行次数函数中，只保留最高阶 （3）如果最高阶存在且不是1，则去除这个项相乘的常数。 上面三部得到的结果就是O的阶 （4）eg：如下例子的复杂度 当i=0时，内循环执行了n次；当n=1时，执行了n-1次，所以总次数为n+(n-1)+(n-2)+...+1 = \(\frac{1}{2}n^2+\frac{1}{2}n\) 。 因此时间复杂度为O(\(n^2\))c for(int i=0;i<n;i++){ for(j=i;j<n;j++){ /* 事件复杂度为O(1)的程序步骤 */ } } （5）又一个例子 操作总次数=1+1+\(\frac{n(n+1)}{2}\),所以时间复杂度为O(\(n^2\))c n++; /* 执行次数为1 */ fun(n); /* 执行次数为1 */ for(int i=0;i<n;i++){ /* 执行次数为如上面的例子 */ for(int j=i;j<n;j++){ /*时间复杂度为O(1)的操作*/ } }
转载于:https://www.cnblogs.com/moonlord/p/5938043.html
