算法初级——时间复杂度

认识时间复杂度
常数时间的操作:一个操作如果和数据量没有关系,每次都是固定时间内完成的操作,叫做常数操作。
时间复杂度为一个算法流程中,常数操作数量的指标。常用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中出现的数;
三个流程,三种时间复杂度的表达…
如何分析好坏?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
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;i<b.length;i++) {
            boolean q = true;
            for(int j = 0;j<a.length;j++) {
                if(a[j] == b[i]) {
                    q = false;
                    break;
                }
            }
            if(q) {
                System.out.print(b[i]+" ");
            }
        }
    }
    //算法流程2 二分查找
    public static void fun2(int[] a,int[] b) {
        for(int i = 0;i<b.length;i++) {
            boolean q = true;
            int left = 0;
            int right = a.length-1;
            while(left<=right) {
                int mid = left+(right-left)/2;//防止越界
                if(a[mid] == b[i]) {
                    q = false;
                    break;
                }else if(a[mid]<b[i]) {
                    left = mid+1;
                }else {
                    right = mid-1;
                }
            }
            if(q) {
                System.out.print(b[i]+" ");
            }
        }
    }
    //算法流程3 排序
    public static void fun3(int[] a,int[] b) {
        Arrays.sort(b);
        int i = 0;
        int j = 0;
        while(i<a.length && j<b.length) {
            if(a[i]<b[j]) {
                i++;
            }else if(a[i]>b[j]) {
                System.out.print(b[j++]+" ");
            }else {
                i++;
                j++;
            }
        }
        while(j<b.length) {
            System.out.print(b[j++]+" ");
        }
    }
   
    //产生测试数组  
    public static int[] testData(int len,int val){  
        int arr[] = new int[len];  
        for (int i = 0; i < arr.length; i++) {  
            arr[i] = (int)(val*Math.random()-val*Math.random());  
        }  
        return arr;  
    }  

    public static void main(String[] args) {
        int []a = testData(10, 20);
        Arrays.sort(a);
        int []b = testData(8, 20);
        System.out.println("a:"+Arrays.toString(a));
        System.out.println("b:"+Arrays.toString(b));
        fun1(a,b);
        System.out.println();
        fun2(a,b);
        System.out.println();
        fun3(a,b);

    }

}
0 条评论
发表一条评论