• 1. 大O表示法
• 递归复杂度 Master theorem
• 2. contain 是否存在
• 3. test

---

1. 大O表示法

• 渐进上界：代表算法执行的最差情况
• 渐进下界 $\Omega(g(n))$：代表算法执行的最佳情况
• 渐进紧界$\Theta(g(n))$

大O表示法

• 表达式中相乘的常量，可以省略，如
  • $f(n) = 100*n^2$ 中的 $100$
• 多项式中数量规模更小（低次项）的表达式，如
  • $f(n)=n^2+n$ 中的 $n$
  • $f(n) = n^3 + n^2$ 中的 $n^2$
• 不同底数的对数，渐进上界可以用一个对数函数 $\log n$ 表示
  • 例如：$log_2(n)$ 可以替换为 $log_{10}(n)$，因为 $log_2(n) = \frac{log_{10}(n)}{log_{10}(2)}$，相乘的常量 $\frac{1}{log_{10}(2)}$ 可以省略
• 类似的，对数的常数次幂可省略
  • 如：$log(n^c) = c * log(n)$

按时间复杂度从低到高

• 黑色横线 $O(1)$，常量时间，意味着算法时间并不随数据规模而变化
• 绿色 $O(log(n))$，对数时间
• 蓝色 $O(n)$，线性时间，算法时间与数据规模成正比
• 橙色 $O(n*log(n))$，拟线性时间
• 红色 $O(n^2)$ 平方时间
• 黑色朝上 $O(2^n)$ 指数时间
• 没画出来的 $O(n!)$

String a = String.format("%d", 12);     // 12

递归复杂度 Master theorem

x不等于c时，T(n) = $O(n^{max(x,c)})$；相等时，T(n) = $O(n^c \log n)$

若有递归式 $$ T(n) = aT(\frac{n}{b}) + O(n^c) $$ 其中

• $T(n)$ 是问题的运行时间，$n$ 是数据规模
• $a$ 是子问题个数
• $T(\dfrac{n}{b})$ 是子问题运行时间，每个子问题被拆成原问题数据规模的 $\dfrac{n}{b}$
• $O(n^c)$ 是除递归外执行的计算

令 $x = \log_{b}{a}$，即 $x = \log_{子问题缩小倍数}{子问题个数}$

那么 $$ T(n) = \begin{cases} \Theta(n^x) & f(n) = O(n^c) 并且 c \lt x\ \Theta(n^x\log{n}) & f(n) = \Theta(n^x)\ \Theta(n^c) & f(n) = \Omega(n^c) 并且 c \gt x \end{cases} $$

例1

$T(n) = 2T(\frac{n}{2}) + n^4$

• 此时 $x = 1 < 4$，由后者决定整个时间复杂度 $\Theta(n^4)$

例2

$T(n) = T(\frac{7n}{10}) + n$

• $a=1, b=\frac{10}{7}, x=0, c=1$
• 此时 $x = 0 < 1$，由后者决定整个时间复杂度 $\Theta(n)$

例3

$T(n) = 16T(\frac{n}{4}) + n^2$

• $a=16, b=4, x=2, c=2$
• 此时 $x=2 = c$，时间复杂度 $\Theta(n^2 \log{n})$

例4

$T(n)=7T(\frac{n}{3}) + n^2$

• $a=7, b=3, x=1.?, c=2$
• 此时 $x = \log_{3}{7} < 2$，由后者决定整个时间复杂度 $\Theta(n^2)$

例5

$T(n) = 7T(\frac{n}{2}) + n^2$

• $a=7, b=2, x=2.?, c=2$
• 此时 $x = log_2{7} > 2$，由前者决定整个时间复杂度 $\Theta(n^{\log_2{7}})$

例6

$T(n) = 2T(\frac{n}{4}) + \sqrt{n}$

• $a=2, b=4, x = 0.5, c=0.5$
• 此时 $x = 0.5 = c$，时间复杂度 $\Theta(\sqrt{n}\ \log{n})$

2. contain 是否存在

contain + getIndex，而不是直接 return true/false.

//判断id在集合中是否存在
public static boolean contains(ArrayList<Student> list, String id) {
    return getIndex(list,id) >= 0;
}

//通过id获取索引的方法
public static int getIndex(ArrayList<Student> list, String id){
    for (int i = 0; i < list.size(); i++) {
        Student stu = list.get(i);
        String sid = stu.getId();
        if(sid.equals(id)){
            return i;
        }
    }
    return -1;
}

3. test

assertIterableEquals(List.of(4, 3, 2, 1), list);

assertEquals(3, list.get(2));

assertThrows(IllegalArgumentException.class, () -> list.get(10));
assertThrows(IllegalArgumentException.class, list::removeFirst);