关于算法增长阶（Order of Growth）的概念与计算方法问询

Hey there! Let's break down all your questions about Order of Growth—since you're diving into this section without prior algorithm analysis experience, these are totally valid and super common confusions. Let's tackle each one clearly:

1. What's the exact definition of n (problem size) in algorithms? #

This is a great spot to clarify! In the Newton's method square root example from SICP, the book’s mention of 0.001 isn’t n—that’s just a fixed precision threshold (a constant, like the k₁/k₂ you guessed).

n represents the size of the problem input that directly affects the algorithm’s resource usage. For the square root function, n is absolutely the input x—since as x grows larger, the number of iterations needed to reach the 0.001 threshold increases (as your Python tests showed: sqrt(2) takes 3 iterations, sqrt(1024) takes 8).

Order of Growth only cares about how resource usage scales as n approaches infinity, so constants like 0.001 don’t change the growth order—they just add a fixed factor we can ignore for asymptotic analysis.

2. What does R(n) actually mean? #

R(n) is an abstract measure of resource consumption tied to problem size n—it’s not tied to specific OS-level operations. You get to define what "resource" means here: it could be the number of arithmetic operations, recursive calls, or even memory slots used.

The key point is: while different operating systems might execute basic operations at different speeds, those differences are all constant factors (e.g., one OS might take 2 cycles for a multiplication, another takes 3). Order of Growth ignores constant factors and lower-order terms, so these implementation-specific details don’t affect whether we classify an algorithm as Θ(log n), Θ(n), etc. We just need to be consistent in how we define R(n) for a given analysis.

3. How do we define a "step" in an algorithm? #

There’s no universal, rigid definition of a "step"—it’s a simplified metric you choose to represent the core work of the algorithm. You could define it as:

• The number of arithmetic operations (additions, multiplications, comparisons)
• The number of times we apply the substitution model (reducing expressions to values)
• The number of recursive/iterative calls made

The only rule is: your definition should capture the part of the algorithm that scales with n. For example, in the square root iterators, counting each full iteration (a good-enough? check plus an improve calculation) as one step works perfectly—since each iteration does a fixed amount of work, the total steps scale with the number of iterations.

4. How to calculate step and space growth orders? Let's use the tree-recursive Fibonacci example. #

Let’s break down both step and space growth for the recursive Fibonacci function (F(n) = F(n-1) + F(n-2)):

Step Growth (Θ(φⁿ))

Each recursive call to F(n) spawns two more calls: one to F(n-1) and one to F(n-2). If you draw this as a recursion tree, every node represents a single function call (each with a constant amount of work: a subtraction and addition).

The total number of nodes in this tree is roughly equal to F(n+1), which is known to grow exponentially with the golden ratio φ = (1+√5)/2 ≈ 1.618. Since F(n) itself is Θ(φⁿ), the total number of steps (function calls + constant work per call) is also Θ(φⁿ).

Space Growth (Θ(n))

Space growth depends on the maximum number of active recursive calls at any time (the depth of the recursion stack). When calculating F(n), we first fully evaluate F(n-1), which requires evaluating F(n-2), and so on down to F(1) or F(0). At the deepest point, the stack will hold n consecutive calls (e.g., F(5) → F(4) → F(3) → F(2) → F(1)). Each call takes a constant amount of space (storing the current n value), so total space scales linearly with n—hence Θ(n).

Code Examples #

Scheme Square Root Implementation

(define (sqrt x) (sqrt-iter 1.0 x))
(define (sqrt-iter guess x)
  (if (good-enough? guess x)
      guess
      (sqrt-iter (improve guess x) x)))
(define (good-enough? guess x)
  (< (abs (- (square guess) x)) 0.001))
(define (improve guess x)
  (average guess (/ x guess)))
(define (average a b)
  (/ (+ a b) 2))
(define (square x) (* x x))

Python Iteration Count Verification

# (Assuming you have a similar sqrt implementation tracking iterations)
In [33]: sqrt(2)  # → 3 iterations to reach result
In [34]: sqrt(4)  # → 4 iterations to reach result
In [35]: sqrt(1024)  # → 8 iterations to reach result

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