Complexity Analysis

input size

1 秒中内 cup 可以做 10^6 ~ 10^7 的操作

如果数据库规模为 100， 那算法可以是 n^3,

如果数据库规模为 1000， 那算法可以是 n^2

input size :

• 1 ~10 算法：O(n!) permutation (search: dfs)

• 1 ~20 算法：O(2^n) combination (search: dfs)

• 10 ~50 算法：O(n^4)

• 10 ~100 算法：O(n^3)

• 100 ~1000 算法：O(n^2)

DP O(n^2) ~O(n^4)

ALL PAIRS SHORTEST PATH O(n^3)

ALL PAIRS /DENSE GRAPH O(n^2)

• 1000 ~10^6 算法：O(nlogn) sorting (heap, divide & conquer)

• 1000 ~10^7 算法：O(n) DP, graph traversal / topological sorting, tree traversal

• 1000 ~10^9 算法：O(sqrt(n)) prime, square sum

• 1000 ~10^9 算法：O(logn) binary search

• 10^6 ~10^9 算法：O(1) math

Graph Traversal

Visited all nodes in List graph

class GraphVister {
    public void traverse(List<GraphNode> graph) {
        for (GraphNode n : graph) {
            if (!n.visted) {
                dfs(n);
            }
        }
    }

    public void dfs(GraphNode node) {
        node.visted = true;
        for (GraphNode n : node.nei) {
            if (!n.visted) {
                dfs(n);
            }
        }
    }
}

class GraphNode {
    public int value;
    public List<GraphNode> nei;
    boolean visited;
    public GraphNode(int v) {
        value = v;
        nei = new ArrayList<>();
        visited = false;
    }
}

1 4 – 5 /
2 3

二叉树和链表，V 和 E 是 1： 1，或者 1： 2， OV + OE = OV 的时间度

图里面， V, E 关系不确定

Given V ：

E min (0) spark graph

E max (v^2) dense graph

 public void dfs(GraphNode node) { // O(v) 个node
        node.visted = true;
        for (GraphNode n : node.nei) { O(E /v) 平均一个 node 的边
            if (!n.visted) {
                dfs(n);
            }
        }
    }

node.visted = true; dfs 会被执行 v 成不变， O(E + V)

• each DFS call itself (not consider next level recursion) is O(E/V + 1)

• each DFS marks one visited

• each node is only marked once

• There are n nodes O(V*(E/V + 1)) = O(V + E) 这里 1 是 node.visted = true; 的复杂度

swap time complexity

// O(n) 
for (int i = 0; i < array.length; i++) {
    while (array[i] != i + 1 && array[i] != array.length + 1) {
        swap(array, i, array[i] - 1); // O(n / n) 平均下来是 O（1）
    }
}
for (int i = 0; i < array.length; i++) {
    if(array[i] != i + 1 ) {
        return i + 1;
    }
}
return array.length + 1;

each swap call puts one element into the right position, swap’s complexity is O(1)

XOR

• x^x = 0
• x^0 = x