复杂度分析

分类

• 时间复杂度
• 空间复杂度

表示形式

• O(1) 常数复杂度
• O(log n) 对数复杂度
• O(n) 线性时间复杂度
• O(n²) 平方
• O(n³) 立方
• O(2ˆn) 指数
• O(n!) 阶乘

举例

O(1)

int n = 1;
System.out.println("input = " + n);

O(log n)

for(int i=1;i<=n;i=i*2){
    System.out.println("index = " + i);
}

O(n)

for(int i=1;i<=n;i++){
    System.out.println("index = " + i);
}

O(n²)

for(int i=1;i<=n;i++){
    for(int j=1;j<=n;j++){
        System.out.println("i = " + i + "j = " + j);
    }
}

O(2ˆn)

for(int i=1;i<=Math.pow(2,n);i++){
    System.out.println("index = " + i);
}

O(n!)

for(int i=1;i<=factorial(n);i++){
    System.out.println("index = " + i);
}

时间复杂度

空间复杂度