算法学习笔记

算法就是解决某一类问题的公式和思想，比如 运算、查找、排序、最优决策、面试 等应用场景。

时间复杂度

时间复杂度是指代码运行的时间，运行时间无法预估，但是我们可以预估代码的 基本操作执行次数。

• T(n) = 3n，执行次数是 线性 的

void main (int n) {
    for (int i = 0; i < n; i++) {
        print("操作1")
        print("操作2")
        print("操作3")
    }
}

• T(n) = 5logn，执行次数是用 对数 计算的

void main (int n) {
    for (int i = n; i > 1; i/=2) {
        print("操作1")
        print("操作2")
        print("操作3")
        print("操作4")
        print("操作5")
    }
}

• T(n) = 2，执行次数是 常量

void main (int n) {
    print("操作1")
    print("操作2")
}

• T(n) = 0.5n² + 0.5n，执行次数是用 多项式 计算的

void main (int n) {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < i; j++) {
            print("操作1")
        }
        print("操作2")
    }
}

空间负责度