Read the algorithm in the data structure

I. Introduction

Before diving deeper into data structures and algorithms, it's essential to understand the general methods of algorithm analysis. Algorithm analysis primarily involves evaluating the time and space complexity of an algorithm. However, sometimes we are more interested in the actual performance of the algorithm during execution. Additionally, algorithm visualization is a valuable skill that helps us better understand how an algorithm works step by step. This technique becomes especially useful when dealing with complex or recursive algorithms.

In this article, we will first discuss how to measure the actual running time of an algorithm through experimental design. Then, we'll explore the concept of time complexity analysis. We'll also introduce a "multiplier experiment" that allows us to predict an algorithm’s performance efficiently. Finally, at the end of this article, we'll work through some common interview questions from top internet companies to reinforce what we've learned and apply our knowledge practically.

II. General Methods of Algorithm Analysis

1. Quantifying the Actual Running Time of an Algorithm

Before discussing time and space complexity, let's first look at how to quantify the actual running time of an algorithm. A common metric for performance is the actual runtime of the algorithm. Usually, this runtime depends on the size of the input problem. For example, sorting 1 million numbers takes longer than sorting 100,000 numbers. Therefore, when observing the runtime of an algorithm, it's important to consider how the runtime grows as the problem size increases.

Let’s take the classic example of the ThreeSum algorithm from the book "Algorithms (4th Edition)" (available on Douban). The code is as follows:

public class ThreeSum {  
    public static int count(int[] a) {  
        int N = a.length;  
        int cnt = 0;  
        for (int i = 0; i < N; i++) {  
            for (int j = i + 1; j < N; j++) {  
                for (int k = j + 1; k < N; k++) {  
                    if (a[i] + a[j] + a[k] == 0) {  
                        cnt++;  
                    }  
                }  
            }  
        }  
        return cnt;  
    }  

    public static void main(String[] args) {  
        int[] a = StdIn.readAllInts();  
        StdOut.println(count(a));  
    }  
}

The classes `StdIn` and `StdOut` used here are available on GitHub: https://github.com/absfree/Algo. The purpose of this code is to count all triplets in the array that sum to zero. The algorithm is straightforward—iterating through the array and checking each triplet. We tested this algorithm using files containing 1,000, 2,000, and 4,000 integers and observed how the runtime changed with the input size.

To measure the runtime, we can record the time before and after the algorithm runs. The difference gives the total runtime. When the process is very fast, we can average multiple runs to reduce error. Below is the code used to measure the runtime of the ThreeSum algorithm:

public static void main(String[] args) {  
    int[] a = In.readInts(args[0]);  
    long startTime = System.currentTimeMillis();  
    int count = count(a);  
    long endTime = System.currentTimeMillis();  
    double time = (endTime - startTime) / 1000.0;  
    StdOut.println("The result is: " + count + ", and takes " + time + " seconds.");  
}

Using 1,000, 2,000, and 4,000 integers as input, the results were:

• The result is: 70, and takes 1.017 seconds. // 1000 integers
• The result is: 528, and takes 7.894 seconds. // 2000 integers
• The result is: 4039, and takes 64.348 seconds. // 4000 integers

From these results, we observe that when the input size doubles, the runtime increases by about 8 times. This suggests that the runtime T(N) of the algorithm is proportional to N³. Later, we’ll revisit this relationship once we’ve covered time complexity analysis.

2. Time Complexity Analysis of the Algorithm

(1) Basic Concepts

Time complexity describes how the runtime of an algorithm grows as the input size increases. There are three main notations used to express this:

• Big O notation (O): Represents the upper bound of the runtime. It gives the worst-case scenario.
• Big Ω notation (Ω): Represents the lower bound of the runtime. It gives the best-case scenario.
• Big Θ notation (Θ): Represents the tight bound, meaning the runtime grows proportionally to the function.

Big O is the most commonly used in algorithm analysis. To understand it better, I recommend reading this article: http://blog.jobbole.com/55184/.

(2) Method of Time Complexity Analysis

We’ll use the ThreeSum algorithm again as an example. The key operation is the `if` statement inside the triple loop. We need to determine how many times this statement is executed. For an array of size N, the number of iterations is roughly N³ / 6. Thus, the time complexity of the algorithm is O(N³).

This matches our earlier hypothesis that the runtime grows proportionally to N³. Time complexity reflects how the runtime increases with the input size. While Big O provides the worst-case upper bound, it is often used to describe the expected performance under normal conditions.

To analyze time complexity, follow two steps:

1. Identify the key operation that dominates the runtime.
2. Analyze how many times this operation is executed.

For example, in the ThreeSum algorithm, the `if` statement is the key operation, and its number of executions determines the overall time complexity.

3. Expected Running Time of the Algorithm

The expected runtime refers to the typical performance of an algorithm under normal circumstances. While the worst-case time complexity is important, the expected runtime is often more relevant for practical applications. For instance, quicksort has a worst-case time complexity of O(N²), but its average case is O(N log N), making it faster in practice than mergesort for many inputs.

4. Doubling Experiment

The doubling experiment is a powerful tool to estimate the growth rate of an algorithm’s runtime. By doubling the input size and measuring the runtime, we can determine the order of magnitude of the algorithm’s performance.

For example, if the runtime increases by a factor of 8 when the input size doubles, the algorithm likely has a time complexity of O(N³). This method helps us predict how an algorithm will scale with larger inputs.

5. Amortized Analysis

Amortized analysis is used when certain operations have high cost but occur infrequently. For example, in a dynamic array, resizing the array is an O(N) operation, but it happens only occasionally. By averaging the cost over many operations, we find that the average cost per operation is O(1).

III. Practice Problems and Interview Questions

Now that we’ve covered the basics of algorithm analysis, let’s apply our knowledge to solve some real-world interview questions.

[Tencent] What is the time complexity of the following algorithm?

int foo(int n) {  
    if (n <= 1) {  
        return 1;  
    }  
    return n * foo(n - 1);  
}

This is a simple recursive function. Each call reduces `n` by 1 until it reaches 1. The number of recursive calls is n, so the time complexity is O(n).

[JD] What is the time complexity of the following function?

void recursive(int n, int m, int o) {  
    if (n <= 0) {  
        printf("%d, %d", m, o);  
    } else {  
        recursive(n - 1, m + 1, o);  
        recursive(n - 1, m, o + 1);  
    }  
}

This function makes two recursive calls at each step. The number of calls grows exponentially, leading to a time complexity of O(2ⁿ).

[Sogou] What is the time complexity of the following algorithm?

x = m;  
y = 1;  
while (x - y > e) {  
    x = (x + y) / 2;  
    y = m / x;  
}  
printf(x);

This is a binary search-like algorithm. The number of iterations is logarithmic in relation to m, so the time complexity is O(log m).

[Sogou] Given the recurrence relation T(n) = 2T(n/2) + n, with T(1) = 1, what is the time complexity?

Using the master theorem, this recurrence corresponds to O(n log n).