Notes on Comic Algorithm (1)

I. Time complexity and space complexity

1.1. Time complexity

• F (n) is said to be of the same order of magnitude as T(n) if there exists a function f(n) such that the limit value of T(n)/f(n) is a constant that is not equal to zero as n approaches infinity. Written as T(n)=O(f(n)), called O(f(n)), O is the asymptotic time complexity of the algorithm, referred to as time complexity. Because progressive time complexity is expressed in capital O, it is also known as the big O notation.
• If the running time is constant, it is expressed by constant 1.
• Only the highest order terms in the time function are retained.
• If the highest order term exists, the function preceding the highest order term is omitted.
• Example:
  • T(n)=3n -> T(n)=O(n)
  • T(n) = 5logn -> T(n)=O(logn)
  • T(n) = 2 -> T(n)=O(1)
  • T (n) = 0.5 n ^ 2 + 0.5 n – > T (n) = O (n ^ 2)
  • If n is large enough: O(1)

1.2 Space Complexity

• Spatial complexity is a measure of the storage space temporarily occupied by an algorithm during its operation, also expressed in large O notation, denoted as S(n) = O(f(n)), where n is the size of the problem and f(n) is a function of the storage space occupied by the algorithm.
• Example:
  • Constant space: O(1)
  • Linear space: O(n)
  • Two dimensional space: O(n^2)
  • Recursive space: If the depth of recursion is N, the space complexity is O(n).

2. Data structure foundation

2.1 an array

An array is an ordered collection of a finite number of variables of the same type, each of which is called an element

Array features:

• Finite, homogeneous, ordered

• Sequential storage (memory cells contiguous)

  💡 ps: Lists are essentially arrays wrapped in Python.

Advantages of ⭐ arrays: efficient random access, with constant time to find the corresponding element by subscript. One efficient algorithm for finding elements is called dichotomy, which takes advantage of arrays.

Disadvantages of ❌ array: It is convenient to insert and delete elements in array. Due to sequential storage, a large number of elements need to be moved to add and delete, affecting efficiency.

📃 Summary: Arrays are suitable for scenarios where there are many read operations but few write operations.

2.2 list

A linked list is a data structure that is physically discontinuous and non-sequential and consists of several nodes.

• One-way list:
  • Each node in a one-way list contains two parts: data, which holds the data, and next, which points to the next node.
  • The first node is called the head node, the last node is called the tail node, and the next pointer to the tail node is null.
• Bidirectional list:
  • Each node in a two-way list has one more prev pointer to the front node than in a one-way list.

List is random storage, each node is distributed in different locations in memory, rely on Pointers, all nodes are associated, flexible and effective use of fragmentary space.

Storage structure (physical structure) : A storage structure is how data elements and their relationships are stored in a computer.

Logical structure: Logical structure is the relationship between data elements.

2.3 the stack

A stack is a linear data structure in which elements can only be entered first and then entered (FILO for short). The earliest entry is called the bottom of the stack, and the last entry is called the top.

Stacks can be implemented as arrays or linked lists.

• Push: A push operation puts a new element on the stack. Only elements can be pushed from the top of the stack. The new element becomes the new top of the stack.

• Out of the stack: A pop operation is an element that is removed from the stack. Only the top of the stack is allowed to be removed from the stack. The previous element becomes the new top of the stack.

  💡 In Python, the append method is equivalent to pushing, and the POP method is equivalent to pushing.

Use of the stack: The output order of the stack is reversed from the input order, so the stack is often used to backtrace “history”, that is, to trace “history” upstream. Breadcrumb navigation.

2.4 the queue

A queue is a linear structure in which the elements in a queue can only be first-in, first-out (FIFO). The exit end of the queue is called the front end, and the entrance end of the queue is called the rear end.

Queues can be implemented using arrays or linked lists.

• Enqueue: To place new elements in a queue, only at the end of the queue. The next position of the new element becomes the end of the queue.
• Dequeue: Removes elements from the queue, only at the head of the queue. The next element in the queue becomes the new head.

Application of queues: The output order of queues is the same as the input order, so queues are usually used for “history” playback, that is, according to the “history” order, “history” is repeated.

2.5 Stack and queue applications

• deque
  • Combining the characteristics of stack and queue, it can be either first in, first out, or first in, then out.
• Priority queue
  • Follow who has the highest priority and who goes out first.

2.6 a hash table

A hash table, also known as a left hash table, is a data structure that provides a mapping between keys and values. As long as a key is given, the corresponding value can be searched efficiently with time complexity close to O(1).

2.6.1 Write Operations (PUT)

• Write operations insert new key-value pairs (also known as entries) into a hash table

2.6.2 Read Operations (GET)

• A read operation is a lookup of a value in a hash table with a given key.

If a hash conflict occurs:

• Hash table in Java uses linked list method. If the current Key is occupied, the next pointer points to the next node
• Hash tables in Python are addressed, and if the Key is currently in use, it looks back until the subscript value is empty.