1. 时间复杂度O(n)
O(n)衡量了算法的增长曲线，也就是程序运行时间和输入大小的关系。
- 设f(n)和g(n)为两个函数，f(n)=O(g(n))成立的条件是：
如果存在一个**常数c**>0, n>=n0>=1，使得f(n)<=c*g(n)，且n>=n0
证明2n+10的时间复杂度是O(n): 2n+10 <= cn，存在c=3,n0=10使得等式成立
- 简单程序分析：
public static double max(double[] nums) {// array size = n
int size = nums.length; // 2 ops
double max = nums[0]; // 2 ops
for (int i = 1; i < size; i++) { // 2 * (n - 1) ops
if (nums[i] > max) { // 2 * (n - 1) ops
max = nums[i]; // 0 to (n - 1) ops
}
}
return max; // 1 op
} // total: 5n ---> runs in O(n)
- 简单递归程序分析：
public int fac(int n) { // n >= 0
if (n == 0) return 1;
return n * fac(n - 1);
}
T(n) = T(n - 1) + b
T(0) = c
推出通项公式T(n) = c + nb，所以时间复杂度为O(n)
其他简单推论：递归输入T(n) = T(n/2) + c的时间复杂度为O(logn), T(n) = 2T(n - 1) + c时间复杂度为O(2^n)，如前面的汉诺塔
2. 测量时间代码
纳秒
long startTime = System.nanoTime();
Arrays.sort(arr);
long timeElapsed = System.nanoTime() - startTime;
System.out.println("Execution time in nanosecond: " + timeElapsed);
微秒
long startTime = System.currentTimeMillis();
Arrays.sort(arr);
long timeElapsed = System.currentTimeMillis() - startTime;
// convert to seconds
// long timeElapsedSecond = TimeUnit.MILLISECONDS.toSeconds(timeElapsed);
System.out.println("Execution time in nanosecond: " + timeElapsed);
>>> timeit('x.append(1)','x=[]', number = 10000)
0.0014090538024902344
3. 时间复杂度和input size的关系
简单加法O(n)级别不同input size的运行时间测试:
public class runtimeTest {
public static double sum(double n) {
long start = System.currentTimeMillis();
long sum = 0;
for (long j = 0; j < n; j++) { // 注意这边j是long，否则会造成死循环（整数溢出）
sum += 1;
}
return (System.currentTimeMillis() - start) / 1000.0;
}
public static void main(String[] args) {
for (int i = 1; i < 11; i++) {
double n = Math.pow(10, i);
double time = 0;
double count = 1;
for (int j = 0; j < 10; j++) {
time += sum(n);
}
System.out.println("10^" + i + ": " + time / count + " s");
}
}
}
// 10^1: 0.0 s
// 10^2: 0.0 s
// 10^3: 0.0 s
// 10^4: 0.001 s
// 10^5: 0.002 s
// 10^6: 0.013000000000000003 s
// 10^7: 0.13499999999999998 s
// 10^8: 1.366 s
// 10^9: 11.797 s
// 10^10: 119.626 s
结论：从10^5开始，时间10倍增加。
程序运行时间1s以下的输入数据规模：
O(n): < 10 ^ 8
O(n^2) < 10 ^ 4 (x ^ 2 = 10 ^ 8)
O(n*logn) < 10 ^ 7 (x * log_7^x = 10 ^ 8)
O(n^2)算法参见454. 4Sum II
实际问题的数据规模需要在这个基础上再除以10或2
算法的时间复杂度和输入规模的关系(假设运行时间上限为1s)：
- 如果输入规模为1000以下，那么设计O(n^2)级别的算法没有问题。所以排序算法在输入规模较小时可以改用O(n^2)的排序算法进行优化。
- 如果输入规模在10^8左右，那么需要设计O(n)或者O(nlogn)级别的算法
4. 关于O(log(n))的区别
log_2 : 二叉树
log_10 : 求整数位数
根据log换底公式log_b^N = log_b^a * log_a^N，log底数的转换为常数倍,所以不管底是多少，时间复杂度都是O(logn)
5. 循环的形式和时间复杂度的关系
简单循环的时间复杂度
public static void runDiffTimeComp() {
int[] arr = {1, 2, 3, 4};
reverse(arr);
arr = new int[]{1, 2, 3, 4, 5};
reverse(arr);
sort(arr);
binarySearch(arr, 2);
reverseNumber(123);
test(10);
System.out.println(isPrime(10));
}
// swap
public static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
// O(n) reverse array
public static int[] reverse(int[] arr) {
int len = arr.length;
for (int i = 0; i < len / 2; i++) {
swap(arr, i, len - 1 - i);
}
return arr;
}
// O(n)
public static void print(int[] arr) {
int len = arr.length;
for (int i = 0; i < len; i++) {
for (int j = 0; j < 10; j++) {
System.out.println(arr[i] + " " + j);
}
}
}
// O(n^2): (n - 1) + (n - 2) + .. + 0 = (n - 1)n/2
public static int[] bsort(int[] arr) {
for (int i = 0; i < arr.length; i++) {
for (int j = 1; j < arr.length - i; j++) {
if (arr[j - 1] > arr[j]) {
swap(arr, j, j - 1);
}
}
}
return arr;
}
// O(n^2): selection sort
public static int[] ssort(int[] arr) {
for (int i = 0; i < arr.length; i++) {
for (int j = i + 1; j < arr.length; j++) {
if (arr[j] > arr[i])
swap(arr, j, i);
}
}
return arr;
}
// O(logn): log_2^n
public static boolean binarySearch(int[] arr, int target) {
int l = 0;
int r = arr.length;
while (l < r) {
int mid = (l + r) >>> 1;
if (arr[mid] == target) {
return true;
} else if (arr[mid] < target)
l = mid + 1;
else
r = mid;
}
return false;
}
// O(logn): log_10^n
public static int reverseNumber(int num) {
int n = num;
int res = 0;
while (n > 0) {
int r = n % 10;
n = n / 10;
res = res * 10 + r;
}
return res;
}
// O(nlogn)
public static void test(int n) {
for (int i = 1; i < n; i += i) // O(log(n))
for (int j = 0; j < n; j++) // O(n)
System.out.print(i + " "); // 1.., 2.., 4.., 8..
}
// O(sqrt(n))
public static boolean isPrime(int n) {
for (int i = 2; i * i < n; i++) {
if (n % i == 0) return false;
}
return true;
}
6. 两倍input size增加测试时间复杂度
input size每次增加两倍，观察runtime的改变
public static int[] generateRandomArray(int len, int l, int r) {
Random rand = new Random();
int[] arr = new int[len];
for (int i = 0; i < len; i++) {
arr[i] = rand.nextInt(r - l + 1) + l;
}
return arr;
}
public static void testTwoTimesIncrement(String name, int a, int b) throws Exception {
Method method = runtimeTest.class.getMethod(name, int[].class);
for (int i = a; i < b; i++) {
int n = (int) Math.pow(2, i); // 2, 4, 8, 16, 32, 64, ...
int[] arr = generateRandomArray(n, 0, 10000000);
long start = System.currentTimeMillis();
method.invoke(null, arr);
double end = (System.currentTimeMillis() - start) / 1000.0;
System.out.println("i: " + i + ", input size: " + n + ", runtime: " + String.format("%10.6e", end) + " s");
}
}
public static void main(String[] args) throws Exception {
testTwoTimesIncrement("reverse", 15, 29);
testTwoTimesIncrement("ssort", 10, 17);
// change method param signature.
testTwoTimesIncrement1("binarySearch", 20, 28);
}
// O(n) reverse() 2 times increment
//i: 22, input size: 4194304, runtime: 1,0e-03 s
//i: 23, input size: 8388608, runtime: 5,0e-03 s
//i: 24, input size: 16777216, runtime: 8,0e-03 s
//i: 25, input size: 33554432, runtime: 1,7e-02 s
//i: 26, input size: 67108864, runtime: 2,8e-02 s
//i: 27, input size: 134217728, runtime: 5,5e-02 s
//i: 28, input size: 268435456, runtime: 1,1e-01 s
// O(n^2) ssort() 4 times increment
//i: 10, input size: 1024, runtime: 6,0e-03 s
//i: 11, input size: 2048, runtime: 9,0e-03 s
//i: 12, input size: 4096, runtime: 4,5e-02 s
//i: 13, input size: 8192, runtime: 1,3e-01 s
//i: 14, input size: 16384, runtime: 4,8e-01 s
//i: 15, input size: 32768, runtime: 1,7e+00 s
//i: 16, input size: 65536, runtime: 6,5e+00 s
//i: 17, input size: 131072, runtime: 2,7e+01 s
//O(logn) binary search slowly increment: (log2n/logn = 1 + log2/logn)
//i: 20, input size: 1048576, runtime: 6,1e+04 ns
//i: 21, input size: 2097152, runtime: 3,3e+04 ns
//i: 22, input size: 4194304, runtime: 2,9e+04 ns
//i: 23, input size: 8388608, runtime: 3,3e+04 ns
//i: 24, input size: 16777216, runtime: 4,1e+04 ns
//i: 25, input size: 33554432, runtime: 4,3e+04 ns
//i: 26, input size: 67108864, runtime: 3,8e+04 ns
//i: 27, input size: 134217728, runtime: 5,4e+04 ns
结论：O(logn)的时间复杂度比O(n)小得多，O(nlogn)相比O(n^2)时间复杂度小的多
7. 均摊时间复杂度分析(ArrayList为例)
import java.util.Arrays;
public class MyArrayList {
private int cap;
private int[] arr;
private int pointer;
public MyArrayList(int cap) {
this.cap = cap;
pointer = 0;
arr = new int[cap];
}
public void add(int e) {
if (pointer >= cap) resize(cap * 2);
arr[pointer++] = e;
}
private void resize(int size) {
System.out.println("resize");
int[] newArr = new int[size];
for (int i = 0; i < pointer; i++) {
newArr[i] = arr[i];
}
cap = size;
arr = newArr;
}
public int pop() {
assert (pointer >= 0);
pointer--;
int res = arr[pointer];
if (pointer <= cap / 4) resize(cap / 2); // change if condition from cap/2 to cap/4(刚好比1/4多一个元素的时候resize)
return res;
}
private void getArray() {
System.out.println(Arrays.toString(arr));
}
public static void main(String[] args) {
MyArrayList list = new MyArrayList(3);
for (int i = 0; i < 9; i++) {
list.add(i);
list.getArray();
}
for (int i = 0; i < 9; i++) {
System.out.println("pointer: " + list.pointer + ", pop :" + list.pop());
list.getArray();
}
}
}
某个时间复杂度较高的方法均摊到其他操作中，如MyArrayList中的resize()方法平分到每一次操作之后，add()的时间复杂度仍然为O(1)。
注意pop的条件是pointer <= cap / 4, 防止复杂度震荡（在同一个点不断调用resize())
output:
[0, 0, 0]
[0, 1, 0]
[0, 1, 2]
resize
[0, 1, 2, 3, 0, 0]
[0, 1, 2, 3, 4, 0]
[0, 1, 2, 3, 4, 5]
resize
[0, 1, 2, 3, 4, 5, 6, 0, 0, 0, 0, 0]
[0, 1, 2, 3, 4, 5, 6, 7, 0, 0, 0, 0]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 0, 0, 0]
pointer: 9, pop :8
[0, 1, 2, 3, 4, 5, 6, 7, 8, 0, 0, 0]
pointer: 8, pop :7
[0, 1, 2, 3, 4, 5, 6, 7, 8, 0, 0, 0]
pointer: 7, pop :6
[0, 1, 2, 3, 4, 5, 6, 7, 8, 0, 0, 0]
pointer: 6, pop :5
[0, 1, 2, 3, 4, 5, 6, 7, 8, 0, 0, 0]
pointer: 5, pop :4
[0, 1, 2, 3, 4, 5, 6, 7, 8, 0, 0, 0]
resize
pointer: 4, pop :3
[0, 1, 2, 0, 0, 0]
pointer: 3, pop :2
[0, 1, 2, 0, 0, 0]
resize
pointer: 2, pop :1
[0, 0, 0]
resize
pointer: 1, pop :0
[0]