Cara mudah untuk mencari Kerumitan Masa Algoritma

Kerumitan masa dianggap sebagai salah satu topik paling sukar untuk pemula yang baru bermula dengan Penyelesaian Masalah. Di sini, saya menyediakan helaian panduan analisis kerumitan masa. Saya harap ini membantu. Sila beritahu saya jika anda mempunyai sebarang soalan.

Lembaran Cheat Analisis Kerumitan Masa

Jadual Rujukan Pantas

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)

Mengenalpasti Corak

1. O(1) - Malar

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

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

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

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

5. O(n²) - Kuadratik

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

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

Kerumitan Masa Operasi Biasa

Operasi Tatasusunan/Senarai

# 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

Kamus/Operasi Set

# 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

Operasi Rentetan

# 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

Analisis Gelung

Gelung Tunggal

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

Gelung Bersarang

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

Berbilang Gelung

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

Analisis Rekursif

Rekursi Linear

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

Rekursi Perduaan

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

Bahagikan & Takluk

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

Pengoptimuman Bendera Merah

Gelung Tersembunyi

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

Fungsi Terbina dalam

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

Petua untuk Analisis

1. Kira gelung bersarang
2. Semak percabangan rekursif
3. Pertimbangkan operasi tersembunyi
4. Cari perpecahan & takluk
5. Semak kerumitan fungsi terbina dalam
6. Pertimbangkan purata vs kes terburuk
7. Perhatikan pembolehubah gelung
8. Pertimbangkan kekangan input

Terima kasih kerana membaca, sila berikan ibu jari pada siaran itu jika anda mendapati ini berguna. Ceria!

Atas ialah kandungan terperinci Cara mudah untuk mencari Kerumitan Masa Algoritma. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!