Algorithm Basics and Analysis Methods

In the world of computer science,Algorithmsis like a recipe for a computer. It is a clear, finite, executable sequence of instructions used to solve a specific problem or complete a particular computational task. Whether it is the navigation software on your phone planning the shortest route for you, or a search engine finding the most relevant webpages from massive amounts of data in milliseconds, both rely on carefully designed algorithms behind the scenes.

Understanding the fundamentals of algorithms and methods of analysis is a key step for every programmer in moving from a code implementer to a problem solver.

This article will systematically introduce you to the core concepts of algorithms and teach you how to scientifically evaluate the pros and cons of an algorithm.

The core characteristics of algorithms

A qualified algorithm must possess the following five basic characteristics. We can understand them using a cooking analogy:

  1. Finiteness: The algorithm must terminate after a finite number of steps. Just as a recipe cannot require you to stir indefinitely until the end of the universe, it must give a clear stopping condition.
  2. Determinism: Every step of the algorithm must have an exact definition, with no ambiguity. For example, "add a pinch of salt" is uncertain, while "add 5 grams of salt" is definite.
  3. Feasibility: Every operation in the algorithm must be basic and executable. You cannot write in a recipe "use your mind to whisk the eggs."
  4. Input: An algorithm has zero or more inputs. These inputs are the objects processed by the algorithm, just like the ingredients needed in a recipe.
  5. Output: An algorithm has one or more outputs. The output is a quantity that has a specific relationship with the input and is the result of the algorithm's execution, just like the final prepared dish.

How to describe an algorithm?

We can describe an algorithm in many ways; the three most common are:

1. Natural language description

Describe the algorithm's steps in human language (e.g., Chinese, English). The advantage is that it is easy to understand, but the disadvantage is that it is not precise enough and can easily cause ambiguity.

Example: Find the maximum value among three numbers.

  1. Compare the first number and the second number, and remember the larger one.
  2. Compare the number remembered in the previous step with the third number.
  3. Output the largest number as the maximum value.

2. Flowchart

Use graphical symbols to represent the control flow of the algorithm. It intuitively shows the logical relationships between steps.

Flowchart description: This diagram clearly shows the decision-making process of the algorithm for finding the maximum of three numbers. Diamonds represent conditional judgments, rectangles represent processing steps, and arrows indicate the direction of program execution.

3. Pseudocode

A description method between natural language and programming language. It uses programming-language-like structures (e.g.,if, for, while), but ignores specific syntax details and focuses on logical expression.

算法：FindMax
输入：三个数字 a, b, c
输出：最大值 max

1.  if a > b then
2.      max = a
3.  else
4.      max = b
5.  end if
6.  if c > max then
7.      max = c
8.  end if
9.  输出 max

4. Programming language implementation

Ultimately, the algorithm needs to be translated into code in some programming language (such as Python, Java, C++) in order to run on a computer.

Example

# Python implementation: Find the maximum of three numbers
def find_max(a, b, c):
    # First compare a and b, assign the larger value to max_value
    if a > b:
        max_value = a
    else:
        max_value = b
    # Then compare max_value with c
    if c > max_value:
        max_value = c
    return max_value

# Test code
print(find_max(5, 9, 3))  # Output: 9
print(find_max(-1, 0, 1)) # Output: 1

Output result:

9
1

Algorithm analysis: How to evaluate the quality of an algorithm?

Designing an algorithm that can solve a problem is only the first step; we also need to determine which algorithm is better. Usually we evaluate from two dimensions:

1. Time complexity

It measuresThe time required for an algorithm to runhow asInput data size (n)grows with the growth of ... What we focus on is not the specific number of seconds, but the growth trend (calledAsymptotic time complexity）。

Comparison of common time complexities:

Complexity Name Example (n = data size) Vivid Metaphor
O(1) Constant Order Accessing array elements by index "Turn on the light". No matter how large the room is, the time to flip the switch is the same.
O(log n) Logarithmic Order Binary Search "Flip through the dictionary". Each time half is eliminated, so the search speed is extremely fast.
O(n) Linear Order Traverse the array Count people. Count person by person; the time is proportional to the total number of people.
O(n log n) Linearithmic Order Quicksort, merge sort "Divide-and-conquer sorting". Much faster than O(n²).
O(n²) Quadratic Order Simple selection sort, bubble sort "Pairwise handshakes". Each person must shake hands with every other person once.
O(2ⁿ) Exponential Order Solving Tower of Hanoi, brute-force enumeration "Cell division". The growth is extremely terrifying; a slightly larger n becomes unbearable.

How to analyze?Focus on loops and recursion.

  • Single loop: usually O(n).
  • Nested loops: usually O(n²) (if both levels are related to n).
  • Binary search strategy: usually O(log n).

2. Space complexity

It measuresThe memory space required for an algorithm to runhow asInput data size (n)grows with the growth of ... In addition to storing the input data itself, it is also necessary to consider the additional arrays, variables, etc. allocated during the algorithm's execution.

Example analysis:

Example

# Example 1: Space complexity O(1)
def find_max_in_list(lst):
    max_val = lst[0]          # Only uses a constant number of extra variables.
    for num in lst:
        if num > max_val:
            max_val = num
    return max_val

# Example 2: Space complexity O(n)
def copy_and_double_list(lst):
    new_list = []             # Allocated a new list of the same length as the input list.
    for num in lst:
        new_list.append(num * 2)
    return new_list

Practical exercise: Analysis and application from the perspective of sorting algorithms

Let's take the classicBubble Sortas an example, comprehensively applying the above knowledge.

Algorithm Idea

Repeatedly traverse the list to be sorted, comparing two adjacent elements at a time, and swap them if they are in the wrong order.

The traversal of the list is repeated until there are no more elements that need to be swapped, which means the list has been sorted. Smaller elements will gradually float to the top of the sequence like bubbles.

Python implementation and line-by-line analysis

Example

def bubble_sort(arr):
    """
Bubble Sort Algorithm
Parameter arr: the list to be sorted
Return value: the sorted list (modified in place, also returned directly)
    """
    n = len(arr)
    # Outer loop: controls how many rounds of "bubbling" are needed overall.
    for i in range(n - 1):
        # Assume this round is already sorted, used for optimization.
        swapped = False
        # Inner loop: performs one round of bubbling, sinking the largest element to the end.
        # After each round, the last i+1 elements are already sorted, so the range is n-1-i.
        for j in range(0, n - 1 - i):
            # If the previous element is larger than the one after it, swap.
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]  # Python's elegant swap syntax.
                swapped = True  # A swap occurred.
        # If not a single swap occurs during this round, the list is fully sorted, so we can exit early.
        if not swapped:
            break
    return arr

# Test data and verification.
test_data = [64, 34, 25, 12, 22, 11, 90]
print("Before sorting:", test_data)
sorted_data = bubble_sort(test_data.copy()) # Use copy to avoid modifying the original list.
print("After sorting:", sorted_data)

# Verify whether the result is correct.
print("Is the sorting correct?", sorted_data == sorted(test_data.copy())) # Should be consistent with Python's built-in sort result.

Output result:

排序前: [64, 34, 25, 12, 22, 11, 90]
排序后: [11, 12, 22, 25, 34, 64, 90]
排序是否正确? True

Algorithm Analysis

  • Time complexity：
    • Worst-case and average-case O(n²): When the list is completely reversed, it is necessary to perform(n-1) + (n-2) + ... + 1 = n(n-1)/2comparisons and swaps.
    • Best-case O(n): When the list is already sorted, addingswappedWith the flag optimization, one traversal is enough to detect no swaps and terminate early.
  • Space complexity O(1): The algorithm only usesi, j, swappedand other fixed-quantity temporary variables, isIn-place sortingAlgorithm.

Practice Tasks

  • Manual Simulation: Use paper and pencil to trace the algorithm, for the list[5, 3, 8, 1]Perform sorting, and write out the list state after each round of bubbling.
  • Complexity Experiment: Modify the test data, and test with already-sorted lists (e.g.,[1,2,3,4,5]) and a completely reversed list (such as[5,4,3,2,1]) to observe the number of loops (you can add a counter in the inner loop).
  • Try to Improve: Can you think of a sorting algorithm that is similar in idea to bubble sort but possibly more efficient? (Hint: each traversal not only bubbles up a maximum bubble, but also bubbles down a minimum bubble.)
other extensions