如何求解2020年大学考试试题的Theta时间复杂度？

Hey there! Let's break down how to solve for Θ (Theta) time complexity using a common university exam-style problem example—since you mentioned this is from your 2020 exam, I'll use two typical scenarios that are frequently tested: recursive relations and nested loops.

Step 1: Get Clear on Θ Notation First #

First off, remember that Θ notation represents the tight bound of an algorithm's runtime. That means it's both an upper (O) and lower (Ω) bound—we're proving the runtime grows exactly at that rate, no faster, no slower.

Step 2: Pick the Right Approach for Your Problem #

Scenario 1: Recursive Relation (Super Common in Exams) #

Suppose your exam problem gives you this recursive relation:
T(n) = 2T(n/2) + n with base case T(1) = Θ(1)

We'll use the Master Theorem—a staple for exam problems like this. Here's how to apply it:
The Master Theorem works for relations of the form T(n) = aT(n/b) + f(n) where a ≥ 1, b > 1, and f(n) is asymptotically positive.

• For our example: a = 2, b = 2, f(n) = n
• Calculate log_b(a) = log₂(2) = 1
• Compare f(n) to n^log_b(a): here, f(n) = n = n¹, which matches exactly (Case 2 of the Master Theorem)
• Case 2 states that if f(n) = Θ(n^log_b(a)), then T(n) = Θ(n^log_b(a) * log n)
• Final result: T(n) = Θ(n log n)

Scenario 2: Nested Iterative Loops #

Another classic exam problem looks like this code snippet:

for i in range(n):
    for j in range(i, n):
        print(i + j)

To find Θ here:

1. Count total operations: The outer loop runs n times. For each i, the inner loop runs n - i times.
2. Sum the operations: n + (n-1) + (n-2) + ... + 1 = n(n+1)/2
3. Simplify asymptotically: This reduces to (n² + n)/2, which is equivalent to n² for large n. So the Θ complexity is Θ(n²)

Step 3: Verify the Tight Bound #

Always double-check that your bound is both upper and lower:

• For the recursive example: We know T(n) can't grow slower than n log n (lower bound Ω(n log n)) and can't grow faster than n log n (upper bound O(n log n)), so it's strictly Θ(n log n).
• For the loop example: The total operations are exactly quadratic, so it's definitely Θ(n²).

Quick Exam Pro Tips #

• For loops: Always write out the exact number of iterations first—don't skip this step, it's easy to make mistakes otherwise.
• For recursion: Memorize the Master Theorem cases—professors love testing these directly.
• Never ignore base cases! For most problems, base cases are Θ(1) unless stated otherwise.

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