YouTip

Basic Algorithms and Analysis Methods

In the world of computer science, an algorithm is like a recipe for a computer — it's a clear, finite, and executable sequence of instructions designed to solve a specific problem or perform a particular computational task. Whether it's a navigation app on your phone calculating the shortest route, or a search engine finding the most relevant web pages from massive data in milliseconds, all rely on carefully designed algorithms. Understanding the fundamentals of algorithms and analysis methods is a crucial step for every programmer moving from being a code implementer to becoming a true problem solver. This article will guide you through the core concepts of algorithms and teach you how to scientifically evaluate their quality. * * *

Core Characteristics of Algorithms

A valid algorithm must possess the following five fundamental characteristics, which we can understand using a cooking analogy: 1. **Finiteness**: The algorithm must terminate after a finite number of steps. Just as a recipe shouldn't require you to stir endlessly until the end of the universe, it must provide clear stopping conditions. 2. **Definiteness**: Each step of the algorithm must be clearly defined without ambiguity. For example, "a little salt" is vague, while "5 grams of salt" is precise. 3. **Feasibility**: Every operation in the algorithm must be basic and executable. You can't write "use telepathy to scramble eggs" in a recipe. 4. **Input**: An algorithm may have zero or more inputs. These are the objects the algorithm processes, just like ingredients required by a recipe. 5. **Output**: An algorithm has one or more outputs. These are quantities related to the input, representing the result of the algorithm’s execution — much like the final dish prepared. * * *

How to Describe an Algorithm?

We can describe an algorithm in multiple ways. The three most common are: ### 1. Natural Language Description Using human language (such as Chinese or English) to explain the steps of the algorithm. The advantage is ease of understanding, but the disadvantage is lack of precision and potential for ambiguity. > **Example**: Find the maximum among three numbers. > > > 1. Compare the first number with the second, and remember the larger one. > 2. Compare the number remembered in the previous step with the third number. > 3. Output the larger number as the maximum. ### 2. Flowchart Using graphical symbols to represent the control flow of the algorithm. It intuitively shows the logical relationships between steps. !(https://example.com/wp-content/uploads/2025/12/dsl-basic-algorithm-tutorial-1.png) Flowchart explanation: This diagram clearly illustrates the decision-making process of the algorithm to find the maximum of three numbers. Diamonds represent conditional checks, rectangles represent processing steps, and arrows indicate the direction of program execution. ### 3. Pseudocode A description method that lies between natural language and programming languages. It uses structures similar to programming languages (like `if`, `for`, `while`), but ignores specific syntax details, focusing instead on logical expression.

Algorithm: FindMax
Input: Three numbers a, b, c
Output: Maximum value 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. Output max

### 4. Programming Language Implementation Ultimately, an algorithm needs to be translated into code in a specific programming language (such as Python, Java, C++) to run on a computer. * * *

Examples

# Python Implementation: Find the Maximum Among 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 results: ``` 9 1 ``` * * *

Algorithm Analysis: How to Evaluate Algorithm Quality?

Designing an algorithm that solves a problem is only the first step. We also need to determine which algorithm is better. Typically, we assess algorithms from two dimensions: ### 1. Time Complexity It measures how the **execution time** of an algorithm grows as the **input size (n)** increases. We don’t care about exact seconds, but rather the growth trend (called **asymptotic time complexity**). **Common Time Complexity Comparison:** | Complexity | Name | Example (n = data size) | Visual Metaphor | | --- | --- | --- | --- | | O(1) | Constant order | Array access by index | **"Turning on a light"**. No matter how big the room, the time to flip the switch remains the same. | | O(log n) | Logarithmic order | Binary search | **"Looking up in a dictionary"**. Eliminate half each time, extremely fast search speed. | | O(n) | Linear order | Traversing an array | **"Counting people"**. Count one by one; time is proportional to total number. | | O(n log n) | Linearithmic order | Quick sort, merge sort | **"Sort by divide and conquer"**. Much faster than O(n²). | | O(n²) | Quadratic order | Simple selection sort, bubble sort | **"Handshakes between pairs"**. Everyone shakes hands with everyone else once. | | O(2ⁿ) | Exponential order | Solving Tower of Hanoi, brute-force enumeration | **"Cell division"**. Growth is terrifyingly fast; even moderately large n becomes unmanageable. | **How to Analyze?** Focus on loops and recursion. * Single loop: Usually O(n). * Nested loops: Usually O(n²) (if both levels depend on n). * Binary strategy: Usually O(log n). ### 2. Space Complexity It measures how the **memory space required** by the algorithm grows as the **input size (n)** increases. Besides storing the input data itself, we must also consider additional arrays, variables, etc., allocated during algorithm execution. **Example Analysis:**

Examples

# Example 1: Space Complexity O(1)

def find_max_in_list(lst):
    max_val = lst  # 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 = []  # Allocates a new list of the same length as input
    for num in lst:
        new_list.append(num * 2)
    return new_list

* * *

Practical Exercise: Understanding Analysis and Application Through Sorting Algorithms

Let’s take the classic **Bubble Sort** as an example to apply the knowledge above comprehensively. ### Algorithm Idea Repeatedly traverse the list to be sorted, comparing adjacent elements pairwise. If their order is incorrect, swap them. This traversal continues until no more swaps are needed, indicating the list is fully sorted. Smaller elements gradually "bubble up" to the top of the list. ### Python Implementation and Line-by-Line Explanation

Examples

def bubble_sort(arr):
    """
    Bubble Sort Algorithm
    Parameters: arr - List to be sorted
    Returns: Sorted list (modifies in-place, returns directly)
    """
    n = len(arr)
    # Outer loop: controls how many rounds of "bubbling" are needed
    for i in range(n - 1):
        # Assume this round is already sorted (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 sorted, so the range is n-1-i
        for j in range(0, n - 1 - i):
            # If the preceding element is greater than the next one, swap them
            if arr > arr[j + 1]:
                arr, arr[j + 1] = arr[j + 1], arr  # Python's elegant swap syntax
                swapped = True  # A swap occurred
        # If no swap happened in this round, the list is already fully sorted; 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 prevent modifying original list
print("After sorting:", sorted_data)

# Verify correctness
print("Is sorting correct?", sorted_data == sorted(test_data.copy()))  # Should match Python's built-in sort result

Output results: ``` Before sorting: [64, 34, 25, 12, 22, 11, 90] After sorting: [11, 12, 22, 25, 34, 64, 90] Is sorting correct? True ``` ### Algorithm Analysis * **Time Complexity**: * **Worst and Average Case O(n²)**: When the list is completely reversed, it requires `(n-1) + (n-2) + ... + 1 = n(n-1)/2` comparisons and swaps. * **Best Case O(n)**: When the list is already sorted, thanks to the `swapped` flag optimization, only one pass is needed to detect no swaps, allowing early termination. * **Space Complexity O(1)**: The algorithm uses only a fixed number of temporary variables (`i`, `j`, `swapped`), making it an **in-place sorting** algorithm. ### Practice Tasks * **Manual Simulation**: Use paper and pen to trace the algorithm step-by-step, sorting the list `[5, 3, 8, 1]`, and write down the state of the list after each bubble pass. * **Complexity Experiment**: Modify the test data to use a fully sorted list (e.g., `[1,2,3,4,5]`) and a completely reversed list (e.g., `[5,4,3,2,1]`). Observe the number of loops (add a counter inside the inner loop to track). * **Try Improving**: Can you think of a sorting algorithm similar in idea to bubble sort but potentially more efficient? (Hint: During each pass, bubble both the maximum and minimum elements simultaneously.)