Skip to content

class401-05.md

Latest commit

 

History

History
67 lines (55 loc) · 4.33 KB

class401-05.md

File metadata and controls

67 lines (55 loc) · 4.33 KB

Linked Lists

Big O: Analysis of Algorithm Efficiency

source

Big O is used to describe the efficiency of an algorithm or function based on two factors:

  1. Running Time - the amount of time a function needs to compelete
  2. Memory Space - the amount of memory resources a function uses
  • inregards to algorithm efficiency, Big O is used to describe the worst case

There are four areas to consider for analysis:

  1. Input Size (n) - refers to parameter size (not necessarily number of parameters)
    • one large array is bigger than two integer perameters
  2. Units of Measurement
    • 3 measurements of TIME
      1. time in milliseconds for function execution
      2. number of operations executed - (lines of code executed in a function)
      3. number of basic operations executed - operation contributing the most running time (usually most consuming operation w/in inner loop)
    • 4 measurements of MEMORY (not as much of a concern as TIME)
      1. space required to hold the algorithm code (bytes)
      2. space required for input data
      3. space required for output data
      4. space required for working during the calculation
  3. Orders of Growth - as n grows, represents the increase in TIME or MEMORY
    • Constant Complexity O(1) - no matter what inputs are thrown at our algorithm, it always uses the same amount of time or space
    • Logarithmic Complexity O(lgn) - complexity growth decreases as n grows
    • Linear Complexity O(n) - size of n directly determines TIME/MEMORY
    • Linearithmic Complexity O(n*lgn) - inearithmic functions grow faster than input size n, but not by much.
    • Quadratic Complexity O(n^2) - grows at a rate of input size n * n, example nested loops
    • Cubic Complexity O(n^3) - grows at a rate of input size n * n * n, usually a more extreme case of quadratic complexity
    • Exponential Complexity O(2^n) - very rapidly growing complexity, such that whatever our input size n, we are performing the same number of iterative or recursive loops as n.
    • Factorial Complexity O(n!) - grow extremely fast, relative to our input size, example number of ways to arrange a deck of cards.
  4. Best Case, Worst Case, and Average Case
    • Worst Case: The efficiency for the worst possible input of size n
    • Best Case: The efficiency for the best possible input of size n
    • Average Case: The efficiency for a “typical” or “random” input of size n

Linked Lists

A Linked List is a sequence of Nodes that are connected/linked to each other, where each Node references the next Node in the link.

  • a linear dynamic data structure
  • use memory efficienty because they are dynamically sized

Vocab:

  • Singly - a Singly linked list means that there is only one reference that points to the Next node.
  • Doubly - a Doubly linked list means that there is a reference to both the Next and Previous node.
  • Circular - doesn’t end with a node pointing to a null value, but instead, has a node that acts as the tail of the list (in place of the conventional head node), and the node after the tail node is the beginning of the list in which the end points to.
  • Node - Nodes are the individual items/links that live in a linked list. Each node contains the data for each link.
  • Next - Each node contains a property called Next. This property contains the reference to the next node.
  • Head - The Head is a reference of type Node to the first node in a linked list.
  • Current - The Current is a reference of type Node to the node that is currently being looked at. When moving through a linked list current will start equal to head.

The best way to approach a traversal is through the use of a while() loop

BigO:

  • traversal O(n)
  • adding a node to the beginning O(1)
  • adding a node in the middle O(n)

Resources