100 字：对数时间复杂度

执行的次数即时间复杂度。只关注循环次数。

若循环嵌套，则要把原来时间复杂度相乘。O(n)与O(n)嵌套，则复杂度为O($n^2$)

如果是两个数据规模m, n那么就不能看谁大取谁了。O(m+n)。



​O(logn)​



时间复杂度即一段代码被执行的次数。比如一段代码被执行了n次，那么这段代码时间复杂度为O(n)。



for i in range(1, n):
      i *= 2

i的取值为$2^0,2^1\dots \dots ,2^n$

直到$2^x$大于n，结束循环。x即为循环执行次数。$2^x=n$, $x=logn$。执行次数约为logn，故时间复杂度为O(logn)。



​O(nlogn)​



for i in range(1, n):
	for j in range(1, n):
		pass



这段代码时间复杂度为n*n, 即O($n^2$)。



for i in range(1, n):
	for j in range(1, n):
		j *= 2



则这段则为n * logn, 即O(nlogn)。