Time complexity and space complexity

Time complexity Big O notation

O(1): indicates the Constant Complexity of the status Constant

Dsmt4 (LOG N): Logarithmic Complexity

O(n): indicates the Linear Complexity of the status

O(n^2): n Square Complexity

O(n^3): n cubic

O(2^n): Exponential Growth

O(n!) : Factorial Factorial

Note: Only look at the highest complexity operations

Requirements:

  1. Note the time complexity and space complexity after writing the program
  2. Complete this procedure with the simplest space and time complexity

Time complexity under recursion

  1. Let me draw a recursion tree for the recursion states

    • F(n) = F(n – 1) + F(n – 2)

      • Interview (direct recursion)

      • int fib(int n)
{
  if (n < 2)
    return n;
  return fib(n - 1) + fib(n - 2); } -- Time complexity: O(k^n) Reason: Each loop is expanded twice as much as the last one note: recursion has double calculations, so caching can be used to avoid double calculationsCopy the code

  2. Master Theorem

    • The function that solves all the recursion
    • Any divide-and-conquer/recursive function can calculate the time complexity
    • There are four keys that are actually available
      • Binary search: the sequence itself is ordered -o (log n)
      • Binary tree traversal: each node is cut only once -o (n)
      • Binary search in ordered two-dimensional matrices: O(n)
      • Merge sort: because the best way to sort all sorts is nlogn -o (nlog n)

  3. To consider

    • Binary tree traversal – pre-ordered, middle-ordered, post-ordered: What is the time complexity?
    • Graph traversal: What is the time complexity? (Same as above)
    • Search algorithm: DFS depth first, BFS breadth first time complexity? (Same as above)
    • Binary search: What is the time complexity?

Third, space complexity

1. Array length

  • If your code has an array open, then the length of the array is basically the space complexity
    • One-dimensional array: O(n)
    • Two-dimensional array: O(n^2)

2. Depth of recursion (special description)

  • The deepest level of recursion is the maximum spatial complexity

3. Climbing stairs

  • Direct recursion

    • Time complexity -o (2^n)
    • Space complexity -o (n)

  • Mnemonic search – plus cached recursion

    • Time complexity -o (n)
    • Space complexity -o (n)

  • Dynamic programming

    • Time complexity -o (n)
    • Space complexity -o (n)

  • Dynamic planning + memory optimization

    • Time complexity -o (n)
    • Space complexity -o (1)