Einfache Möglichkeit, die Zeitkomplexität eines Algorithmus zu ermitteln

Zeitkomplexität gilt als eines der schwierigsten Themen für Anfänger, die gerade erst mit der Problemlösung beginnen. Hier stelle ich den Spickzettel zur Zeitkomplexitätsanalyse zur Verfügung. Ich hoffe, das hilft. Bitte lassen Sie mich wissen, wenn Sie Fragen haben.

Cheatsheet zur Zeitkomplexitätsanalyse

Kurzreferenztabelle

O(1)       - Constant time
O(log n)   - Logarithmic (halving/doubling)
O(n)       - Linear (single loop)
O(n log n) - Linearithmic (efficient sorting)
O(n²)      - Quadratic (nested loops)
O(2ⁿ)      - Exponential (recursive doubling)
O(n!)      - Factorial (permutations)

Muster erkennen

1. O(1) – Konstante

# Look for:
- Direct array access
- Basic math operations
- Fixed loops
- Hash table lookups

# Examples:
arr[0]
x + y
for i in range(5)
hashmap[key]

2. O(log n) – Logarithmisch

# Look for:
- Halving/Doubling
- Binary search patterns
- Tree traversal by level

# Examples:
while n > 0:
    n = n // 2

left, right = 0, len(arr)-1
while left <= right:
    mid = (left + right) // 2

3. O(n) – Linear

# Look for:
- Single loops
- Array traversal
- Linear search
- Hash table building

# Examples:
for num in nums:
    # O(1) operation
    total += num

for i in range(n):
    # O(1) operation
    arr[i] = i

4. O(n log n) – Linearithmisch

# Look for:
- Efficient sorting
- Divide and conquer
- Tree operations with traversal

# Examples:
nums.sort()
sorted(nums)
merge_sort(nums)

5. O(n²) – Quadratisch

# Look for:
- Nested loops
- Simple sorting
- Matrix traversal
- Comparing all pairs

# Examples:
for i in range(n):
    for j in range(n):
        # O(1) operation

# Pattern finding
for i in range(n):
    for j in range(i+1, n):
        # Compare pairs

6. O(2ⁿ) – Exponentiell

# Look for:
- Double recursion
- Power set
- Fibonacci recursive
- All subsets

# Examples:
def fib(n):
    if n <= 1: return n
    return fib(n-1) + fib(n-2)

def subsets(nums):
    if not nums: return [[]]
    result = subsets(nums[1:])
    return result + [nums[0:1] + r for r in result]

Häufige zeitliche Komplexität von Vorgängen

Array-/Listenoperationen

# O(1)
arr[i]              # Access
arr.append(x)       # Add end
arr.pop()           # Remove end

# O(n)
arr.insert(i, x)    # Insert middle
arr.remove(x)       # Remove by value
arr.index(x)        # Find index
min(arr), max(arr)  # Find min/max

Wörterbuch-/Set-Operationen

# O(1) average
d[key]              # Access
d[key] = value      # Insert
key in d            # Check existence
d.get(key)          # Get value

# O(n)
len(d)              # Size
d.keys()            # Get keys
d.values()          # Get values

String-Operationen

# O(n)
s + t               # Concatenation
s.find(t)           # Substring search
s.replace(old, new) # Replace
''.join(list)       # Join

# O(n²) potential
s += char           # Repeated concatenation

Schleifenanalyse

Einzelne Schleife

# O(n)
for i in range(n):
    # O(1) operations

# O(n/2) = O(n)
for i in range(0, n, 2):
    # Skip elements still O(n)

Verschachtelte Schleifen

# O(n²)
for i in range(n):
    for j in range(n):
        # O(1) operations

# O(n * m)
for i in range(n):
    for j in range(m):
        # Different sizes

# O(n²/2) = O(n²)
for i in range(n):
    for j in range(i, n):
        # Triangular still O(n²)

Mehrere Schleifen

# O(n + m)
for i in range(n):
    # O(1)
for j in range(m):
    # O(1)

# O(n + n²) = O(n²)
for i in range(n):
    # O(1)
for i in range(n):
    for j in range(n):
        # O(1)

Rekursive Analyse

Lineare Rekursion

# O(n)
def factorial(n):
    if n <= 1: return 1
    return n * factorial(n-1)

Binäre Rekursion

# O(2ⁿ)
def fibonacci(n):
    if n <= 1: return n
    return fibonacci(n-1) + fibonacci(n-2)

Teile und herrsche

# O(n log n)
def mergeSort(arr):
    if len(arr) <= 1: return arr
    mid = len(arr) // 2
    left = mergeSort(arr[:mid])
    right = mergeSort(arr[mid:])
    return merge(left, right)

Rote Flaggen bei der Optimierung

Versteckte Schleifen

# String operations
for c in string:
    newStr += c  # O(n²)

# List comprehension
[x for x in range(n) for y in range(n)]  # O(n²)

Integrierte Funktionen

len()           # O(1)
min(), max()    # O(n)
sorted()        # O(n log n)
list.index()    # O(n)

Tipps zur Analyse

1. Verschachtelte Schleifen zählen
2. Rekursive Verzweigung prüfen
3. Berücksichtigen Sie versteckte Vorgänge
4. Suchen Sie nach „Teile und herrsche“
5. Überprüfen Sie die Komplexität der integrierten Funktionen
6. Betrachten Sie den Durchschnitt gegenüber dem schlimmsten Fall
7. Achten Sie auf Schleifenvariablen
8. Berücksichtigen Sie Eingabebeschränkungen

Vielen Dank fürs Lesen. Bitte geben Sie dem Beitrag einen Daumen nach oben, wenn Sie ihn hilfreich fanden. Prost!

Das obige ist der detaillierte Inhalt vonEinfache Möglichkeit, die Zeitkomplexität eines Algorithmus zu ermitteln. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!