几种情况下的时间复杂度

1. for循环

（1）单层for循环

一般情况下，一层for循环时间复杂度为O(N)，因为for循环通常用于遍历，因此遍历一个长度为N的列表，复杂度通常为O(N)。

（2）嵌套for循环

单层for循环复杂度为O(N)，那么两层的嵌套for循环时间复杂度应该为O(N²)。实时真的是这样吗？我们来看个例子：

for loop example 1：

首先先是来说说上一节的那个嵌套for循环吧：

public static boolean findStupid(String[] input) {
	for(int i=0; i<input.length; i+=1) {
		for(int j=i+1; j< input.length; j+=1) {
			if(input[i].equals(input[j])) {
				return true;
			}
		}
	}
	return false;
}

根据我们上一节的讨论结果，这个for循环是一个时间复杂度为O(N²)的嵌套循环

for loop example 2:

public static void printParty(int N) {
	for(int i=1; i<=N; i=i*2) {
		for(int j=0; j<i; j++) {
			System.out.println("hello");
		}
	}
}

注意到这里外层for循环的i增长方式为i = i * 2，而内层循环变量j的增长方式为j = j + 1，我们对整个循环进行分析：

相信大家也找到规律了，那么对于这种看似没有规律的情况我们该怎样得到时间复杂度呢？
这里我们就要用到O()的定义了，找N的几次方中可以涵盖这一变化规律

可以推断出，当N趋近无穷大时，0.5N和2N可以很好的将C(N)包含起来，所以C(N)的复杂度就是O(N)
通过这两个例子的对比，我们可以发现，实际上嵌套形式的for循环的时间复杂度是不确定的，需要根据情况进行定夺

recursion（递归）

为了研究递归的时间复杂度，我们来看一个最直接的递归的例子吧：

public static int f3(int n) {
        if(n<=1) {
            return 1;
        }
        return f3(n-1) + f3(n-1);
    }

首先我们来分析一下这个方法的作用：

1. 若n<=1，直接返回1
2. 若n>1，重复执行该方法，一步步分解直至满足n<=1。

因此该程序生成一个分枝状结构，假设我们的输入为N，则我们实际返回的值为2^N-1：
（画图的时候画错了。。。图上的N应该是2^N-1)

假设每次递归所需时间相同，那么总时间为：(1+2+4+8+…+2^N-1) = 2^N-1-1（等比数列求和公式），所以时间复杂度为O(2^N)。