2-2-函数调用时间复杂度分析

案例一：

public static void main(String[] args) {
    int n=100;
    for (int i = 0; i < n; i++) {
        show(i);
    }
}
private static void show(int i) {
    System.out.println(i);
}

show方法的时间复杂度为O(1),main方法的时间复杂度是O(n)

案例二：

public static void main(String[] args) {
    int n=100;
    for (int i = 0; i < n; i++) {
        show(i);
    }
}
private static void show(int i) {
    for (int j = 0; j < i; i++) {
        System.out.println(i);
    }
}

在main方法中，有一个for循环，循环体调用了show方法，由于show方法内部也有一个for循环

所以show方法的时间复杂度为O(n)，main方法的时间复杂度为O(n^2)

案例三：

public static void main(String[] args) {
    int n=100;
    show(n);
    for (int i = 0; i < n; i++) {
        show(i);
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            System.out.println(j);
        }
    }
}
private static void show(int i) {
    for (int j = 0; j < i; i++) {
        System.out.println(i);
    }
}

在show方法中，有一个for循环，所以show方法的时间复杂度为O(n),在main方法中，show(n)这行代码内部执行的次数为n，第一个for循环内调用了show方法，所以其执行次数为n^2,第二个嵌套for循环内只执行了一行代码，

所以其执行次数为n^2,那么main方法总执行次数为n+n^2+n^2=2n^2+n。

根据大O推导规则，去掉n保留最高阶项，并去掉最高阶项的常数因子2，所以最终main方法的时间复杂度为O(n^2)

最坏情况

public int search(int num){
    int[] arr={11,10,8,9,7,22,23,0};
    for (int i = 0; i < arr.length; i++) {
        if (num==arr[i]){
            return i;
        }
    }
    return -1;
}