Data Structure and Algorithm Notes (1)

READ COUNT(TIMES)

The farther backward you can look, the farther forward you will see.

Winston Churchill

Why do we need computational complexity analysis?

  • The limitation of post-hoc analysis

    1. The performance will vary according to different hardwares.
    2. The size of the data or the way the data is structured will also impact the performance.

  • Big O notation

    On the contrary, the complexity analysis is platform-independent. There are two ways of doing complexity analysis, which are time complexity and space complexity. Big O notation, Big-omega notation and Big-theta notation are used to estimate the complexity function for arbitrarily large input. In this notes, I am only use the Big O notation to analysis the algorithm.
    $$\mathcal{T}(n)=\mathcal{O}({f}(n))$$

Basic Algorithm

  • Sort

    1. Selection Sort
    2. Insertion Sort
    3. Bubble Sort

  • Graph

    1. Construct a Graph
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      graph = {
          'A': ['B', 'F'],
          'B': ['C', 'I', 'G'],
          'C': ['B', 'I', 'D'],
          'D': ['C', 'I', 'G', 'H', 'E'],
          'E': ['D', 'H', 'F'],
          'F': ['A', 'G', 'E'],
          'G': ['B', 'F', 'H', 'D'],
          'H': ['G', 'D', 'E'],
          'I': ['B', 'C', 'D'],
      }
    2. BFS
      • Use a queue to traverse the vertex and its neighbour
      • Use a set to record the visited vertex
        1
        2
        3
        4
        5
        6
        7
        8
        9
        10
        11
        12
        13
        14
        15
        16
        17
        18
        19
        20
        21
        22
        from collections import deque
        """
        q = [A, ] -> q = []
        cur = {A: ['B', 'F']}
        visited = {} -> visited = {'A'}
        q = [] -> q = ['B', 'F']
        """
        def bfs(graph, start):
            res = []
            q = deque([start, ])
            visited = set()
            while q:
                cur = q.popleft()
                if cur not in visited:
                  res.append(cur)
                  visited.add(cur)
                  for node in graph[cur]:
                      q.append(node)
                      
            return res
                      
        print(bfs(GRAPH, 'A'))
    3. DFS
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      def dfs(graph, start):
        res = []
        visited = set()
        helper(res, graph, start, visited)
        return res 
        
      def helper(res, graph, start, visited):
          if start not in visited:
              res.append(start)
              visited.add(start)
          
          for node in graph[start]:
              if node not in visited:
                  helper(res, graph, node, visited)
                  
      print(dfs(GRAPH, 'A'))

    4. LeetCode

      126, 127

  • Tree

  • Binary Search Tree(BST)

  • Reference

    1. Python Data Structure and Algorithm(in Chinese).