基于统计方法确定冒泡排序程序的近似时间复杂度

Let's break this down step by step—you're on the right track, but the tools and approach you used might not be aligned with what time complexity actually measures (asymptotic growth behavior, not absolute fit or distribution matching).

First, let's ground this in theory: bubble sort is a comparison-exchange sort with worst and average-case time complexity of O(n²). Logarithmic complexity (O(log n)) doesn't make sense here—those apply to algorithms like binary search that split problem sizes exponentially. So we should focus first on validating the quadratic trend, since that's the expected behavior.

Why Your Current Approach Failed #

1. numpy.polyfit with raw data is misleading
   Polynomial fitting with raw time values includes noise from constant overhead (like array initialization) and linear terms (loop setup, function calls). These terms dominate at small n and skew your quadratic coefficient, even though they become negligible as n grows.

2. Kolmogorov-Smirnov (KS) test is the wrong tool
   KS checks if two datasets come from the same distribution—but time complexity is about how runtime scales with input size, not the distribution of runtime values. This test simply isn't designed to validate growth trends.

A Rigorous, Accurate Method to Validate Time Complexity #

1. Start with Log-Log Transformation & Linear Regression #

Time complexity of the form O(n^k) translates to a linear relationship when you take the natural log of both runtime t and input size n:

If t ≈ C * n^k (where C is a constant factor), then ln(t) ≈ ln(C) + k * ln(n)

For your data:

• Calculate ln(n) for each input size (e.g., ln(10000) ≈ 9.21, ln(100000) ≈ 11.51)
• Calculate ln(t) for each runtime (e.g., ln(9.37) ≈ 2.24, ln(1091.26) ≈ 7.00)
• Fit a linear regression to these (ln(n), ln(t)) points.

The slope of this line will be your estimated k. For bubble sort, this slope should be very close to 2. Looking at your data:

• The ratio t(20000)/t(10000) ≈ 37.69/9.37 ≈ 4.02, which is almost exactly (20000/10000)^2 = 4
• t(30000)/t(20000) ≈ 85.13/37.69 ≈ 2.26, matching (3/2)^2 = 2.25
• Even at the upper end, t(100000)/t(90000) ≈ 1091.26/873.36 ≈ 1.25, which is close to (10/9)^2 ≈ 1.23

This already tells you the quadratic trend is holding—linear regression on log-transformed data will formalize this with a high R² value (near 1) and a slope statistically indistinguishable from 2.

2. Use Residual Analysis to Isolate Dominant Terms #

If you still want to use polynomial fitting on raw data:

• Fit a quadratic model t = a*n² + b*n + c
• Compute the residuals: residual = t - (a*n²)
• Plot these residuals against n—they should form a roughly linear line (showing the b*n + c terms are negligible compared to a*n² as n increases). This confirms the quadratic term is the dominant contributor to runtime.

3. Control for Measurement Noise #

Your runtime values have small fluctuations (e.g., system load, cache effects) that can skew fits. Fix this by:

• Running each test 10-20 times and taking the mean runtime (not a single measurement)
• Ensuring a consistent test environment: close background apps, disable dynamic CPU scaling, and use the same random seed for array generation to avoid worst/best-case skew.

4. Focus on Asymptotic Behavior, Not Small n #

Time complexity describes how runtime behaves as n → ∞. Small n values are heavily influenced by constant overhead, so you can optionally exclude the first 1-2 data points (e.g., n=10000, n=20000) when fitting to focus on the asymptotic trend.

Example of What You'll See #

When you run the log-log linear regression on your data, you'll get:

• A slope of ~2.0 (the exact value might be 1.99 or 2.01 due to noise)
• An R² score of >0.999, indicating an almost perfect linear fit

This is definitive proof that your bubble sort implementation follows O(n²) time complexity.

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