求插入排序循环最坏情况下的阶与增长函数

Hey there! Let’s break this down step by step—this is the core logic of insertion sort, so we can walk through the worst-case analysis together to get clear answers.

Step 1: Understand the Loop Behavior in Worst Case #

First, let’s confirm: when your input array is in descending order (the worst case you’re focusing on), every element we process needs to be shifted all the way to the start of the sorted portion of the array. Let’s break down the two loops:

• The outer for loop runs from next = 1 to next = n-1 (since array.length is n), so it executes n-1 total iterations.
• The inner while loop does the heavy lifting. For each next, since the array is reversed, value (the element we’re inserting) is smaller than every element before it. That means the while loop will run next times per outer iteration—we have to shift every element from index next-1 down to 0 to make space for the new element.

Step 2: Calculate Total Critical Operations #

To find the growth function, we sum up the number of inner loop executions across all outer loop runs. This is the sum of the first n-1 positive integers:

• When next = 1: inner loop runs 1 time
• When next = 2: inner loop runs 2 times
• ...
• When next = n-1: inner loop runs n-1 times

The formula for this sum is:

Total operations = 1 + 2 + 3 + ... + (n-1) = (n-1)*n/2

Simplified, this becomes (n² - n)/2.

Step 3: Define Growth Function and Order #

• Growth Function: The exact count of critical operations (comparisons and shifts) in the worst case is f(n) = (n² - n)/2. This function directly describes how the number of operations grows as the input size n increases.
• Order (Asymptotic Complexity): When talking about the "order" of an algorithm, we focus on the dominant term as n becomes very large. The n² term here dominates the -n term, so we drop lower-order terms and constants. This gives us a worst-case time complexity of O(n²) (big O notation), meaning the algorithm has a quadratic order.

Quick Test Case Verification #

To double-check, try small values of n:

• n=3: total operations = 1+2=3, which matches (9-3)/2=3
• n=4: 1+2+3=6, which matches (16-4)/2=6
• n=5: 1+2+3+4=10, which matches (25-5)/2=10

This lines up perfectly with our formula, so you can trust the math here!

内容的提问来源于stack exchange，提问作者GainzNerd