Un moyen simple de trouver la complexité temporelle d'un algorithme

La complexité temporelle est considérée comme l'un des sujets les plus difficiles pour les débutants qui débutent tout juste en résolution de problèmes. Ici, je fournis l'aide-mémoire pour l'analyse de la complexité temporelle. J'espère que cela aide. S'il vous plaît laissez-moi savoir si vous avez des questions.

Aide-mémoire pour l'analyse de la complexité temporelle

Tableau de référence rapide

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)

Identifier les modèles

1. O(1) - Constante

# 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) - Logarithmique

# 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) - Linéaire

# 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) - Linéarithmique

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

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

5. O(n²) - Quadratique

# 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ⁿ) - Exponentiel

# 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]

Complexité temporelle des opérations courantes

Opérations sur les tableaux/listes

# 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

Opérations de dictionnaire/ensemble

# 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

Opérations sur les chaînes

# 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

Analyse de boucle

Boucle unique

# 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)

Boucles imbriquées

# 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²)

Plusieurs boucles

# 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)

Analyse récursive

Récursion linéaire

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

Récursion binaire

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

Diviser et conquérir

# 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)

Drapeaux rouges d’optimisation

Boucles cachées

# 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²)

Fonctions intégrées

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

Conseils pour l'analyse

1. Compter les boucles imbriquées
2. Vérifiez le branchement récursif
3. Considérez les opérations cachées
4. Recherchez diviser pour régner
5. Vérifier la complexité des fonctions intégrées
6. Considérez la moyenne par rapport au pire des cas
7. Surveillez les variables de boucle
8. Considérez les contraintes de saisie

Merci d'avoir lu, merci de laisser un pouce bleu sur le message si vous avez trouvé cela utile. Bravo !

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!