认识时间复杂度
常数时间的操作:一个操作如果和数据量没有关系,每次都是固定时间内完成的操作,叫做常数操作。
时间复杂度为一个算法流程中,常数操作数量的指标。常用O(读作big O)来表示。具体来说,在常数操作数量的表达式中,只要高阶项,不要低阶项,也不要高阶项的系数,剩下的部分如果记为f(N),那么时间复杂度为O(f(N))。
评价一个算法流程的好坏,先看时间复杂度的指标,然后再分析不同数据样本下的实际运行时间,也就是常数项时间。
一个简单的理解时间复杂度的例子
一个有序数组A,另一个无序数组B,请打印B中的所有不在A中的数,A数组长度为N,B数组长度为M。
算法流程1:对于数组B中的每一个数,都在A中通过遍历的方式找一下;
算法流程2:对于数组B中的每一个数,都在A中通过二分的方式找一下;
算法流程3:先把数组B排序,然后用类似外排的方式打印所有在A中出现的数;
三个流程,三种时间复杂度的表达...
如何分析好坏?
import java.util.Arrays; /** 时间复杂度例子 一个有序数组A,另一个无序数组B,请打印B中的所有不在A中的数,A数 组长度为N,B数组长度为M。 */ public class 时间复杂度 { //算法流程1 遍历 public static void fun1(int[] a,int [] b) { for(int i = 0;ib[j]) { System.out.print(b[j++]+" "); }else { i++; j++; } } while(j