I. In-Class Exercises

This lesson has no in-class programming exercises. The focus is on learning the basic concepts and evaluation methods of algorithms.

Study Guide

• L2 Course Study Guide (PDF)

II. Knowledge Summary

✨ Core Ideas of Algorithms

An algorithm is a method for solving problems using programs. It is a finite, well-defined set of operational steps used to solve a specific problem or complete a specific task within a finite amount of time.

A data structure is a way of organizing and manipulating data. Algorithms and data structures are the two pillars of programming — they complement each other. Good data structures can make algorithms more efficient, and good algorithms require suitable data structures to support them.

✨ Algorithm Description

Description Methods

Algorithms can be described in the following three ways:

1. Natural language description: Describes algorithm steps in everyday language — easy to understand but not precise enough
2. Flowchart description: Uses graphical symbols to represent algorithm steps and flow — intuitive and clear
3. Pseudocode description: Falls between natural language and programming language — balances readability and precision

Algorithm Description Example

Problem: How to determine whether a number n is odd or even?

Natural language description:

1. Divide the number by 2 and check the remainder
2. If the remainder is 0, the number is even
3. If the remainder is 1, the number is odd

Flowchart description:

Pseudocode description:

IF n % 2 == 0 THEN
    Output Even
ELSE
    Output Odd

✨ Algorithm Complexity Analysis

The main criteria for evaluating an algorithm include:

• Correctness: The algorithm correctly solves the problem and produces correct output for all valid inputs
• Definiteness: Every step of the algorithm has a clear meaning with no ambiguity
• Scalability: The algorithm can handle input data of varying sizes
• Time Complexity: The time (number of steps) required to execute the algorithm
• Space Complexity: The storage space required during algorithm execution

Time Complexity

Time complexity describes the number of steps or operations required to execute an algorithm and is an important metric for measuring algorithm efficiency.

How to express time complexity:

• Described using Big O notation
• If the complexity depends on the data size, n is used to represent the data size

Common algorithm time complexities:

Space Complexity

Space complexity describes the amount of temporary storage space used during algorithm execution and is also an important metric for measuring algorithm efficiency.

How to express space complexity:

• Described using Big O notation
• If the complexity depends on the data size, n is used to represent the data size

In competitive programming, time complexity is usually the primary concern, but you also need to ensure that space complexity does not exceed the memory limit specified by the problem.

✨ Algorithm Analysis Execution Example

Below is a concrete example demonstrating how to analyze time complexity step by step.

Problem: In an array of length n, find all pairs (i, j) such that arr[i] + arr[j] == target.

1for (int i = 0; i < n; i++) {        // Outer loop executes n times
2    for (int j = i + 1; j < n; j++) { // Inner loop executes ~n/2 times (average)
3        if (arr[i] + arr[j] == target) {
4            cout << i << " " << j << endl;
5        }
6    }
7}

Step-by-step analysis:

1. When i=0, the inner loop executes n-1 times
2. When i=1, the inner loop executes n-2 times
3. When i=2, the inner loop executes n-3 times
4. ...
5. When i=n-2, the inner loop executes 1 time
6. Total executions = (n-1) + (n-2) + ... + 1 = n(n-1)/2
7. Dropping constants and lower-order terms, the time complexity is O(n²)

Comparing with the data scale table: O(n²) corresponds to a data scale of n<10000, so when n exceeds 10000, this algorithm may time out, and a more efficient approach should be considered.

✨ Application Scenarios of Algorithms

• Competitive Programming (OI/ICPC): Almost all competition problems require analyzing time complexity to choose the right algorithm and avoid time limit exceeded (TLE).
• Software Development: When processing large amounts of data, algorithm efficiency directly affects user experience. For example, search engines need to return results within milliseconds.
• Interviews and Tests: In technical interviews, interviewers typically ask candidates to analyze the time and space complexity of algorithms.
• Everyday Problems: Sorting, searching, pathfinding, and other everyday problems are all supported by classic algorithms.

✨ Problem-Solving Steps for Algorithms

When you encounter a problem, how do you determine what complexity of algorithm to use?

Step 1: Check the data scale. The problem usually specifies the range of n. Use the table below to determine the acceptable time complexity:

• n ≤ 20 → Can use O(2ⁿ) brute-force search
• n ≤ 500 → Can use O(n³) algorithms
• n ≤ 10000 → Need O(n²) or better
• n ≤ 100000000 → Need O(n) or O(nlogn)

Step 2: Choose an algorithm. Once you have determined the acceptable complexity, choose a suitable algorithm to implement it.

Step 3: Verify. Roughly estimate the number of operations in your code to ensure it does not exceed 10^8 (generally, about 10^8 simple operations can be executed in 1 second).

Example: The problem gives n ≤ 1000, time limit 1 second.

• O(n³) = 10^9 → TLE
• O(n²) = 10^6 → Acceptable
• Therefore, choose an O(n²) or better algorithm

✨ Common Mistakes with Algorithms

1. Confusing time complexity with actual running time: O(n²) does not mean exactly n² operations — it describes the growth trend. Constant factors also affect actual speed but are ignored in complexity analysis.
2. Judging complexity solely by the number of loop levels: Two nested loops do not necessarily mean O(n²). For example, the total number of inner loop executions might be O(n) rather than O(n²) — specific analysis is required.
3. Ignoring space complexity: Declaring an array of size 10^8 might be fine in terms of time, but it exceeds memory limits. An array of 10^8 int elements requires about 400MB of memory.
4. Forgetting about I/O time: cin/cout with large amounts of data can be slow. In competitive programming, you can use ios::sync_with_stdio(false) and cin.tie(0) to speed things up.

III. Homework

Knowledge Quiz

• Algorithm Overview - Quiz