۱۴۰۵ آبان ۲۶, سه‌شنبه
دلار آمریکا۲۶۷٬۹۰۰▼ ۰٫۳٪یورو۲۹۴٬۷۶۰▼ ۰٫۵۵٪درهم امارات۷۲٬۹۱۶▼ ۰٫۴۲٪سکه امامی۲۵۱٬۸۵۰٬۰۰۰▲ ۰٫۵۲٪طلای ۱۸ عیار (گرم)۲۴٬۶۵۸٬۶۰۰▲ ۰٫۳۷٪انس طلا۳٬۸۵۹ $▼ ۰٫۱۶٪تتر۲۶۸٬۹۹۹▼ ۰٫۱۵٪بیت‌کوین۶۵٬۰۱۸ $▼ ۰٫۲۸٪اتریوم۱٬۸۲۴ $▼ ۰٪سولانا۷۳٫۷۶ $▲ ۳٫۱۶٪اپل۳۵۲٫۷۸ $▼ ۰٫۹۸٪انویدیا۱۵۶٫۱۴ $▼ ۴٫۱۲٪مایکروسافت۵۱۷٫۹۹ $▼ ۱٫۱۲٪آلفابت (گوگل)۲۸۳٫۷۲ $▼ ۴٫۰۷٪تسلا۳۷۹٫۷۴ $▼ ۲٫۶۹٪شاخص نزدک۲۴٬۵۱۰ $▼ ۲٫۴۹٪
نرخ ارز

ساختمان داده و الگوریتم به زبان ساده؛ از Big O تا کد پایتون

ساختمان داده و الگوریتم به زبان ساده: پیچیدگی Big O، لیست، پشته، صف، جدول هش، درخت، هیپ، گراف و جست‌وجوی دودویی با مثال‌های قابل‌اجرای پایتون.

کاور گرافیکی DevNA با عنوان «Big O»: ساختمان داده و الگوریتم به زبان ساده
کاور گرافیکی DevNA با عنوان «Big O»: ساختمان داده و الگوریتم به زبان ساده
فهرست مطالب
  1. ساختمان داده و الگوریتم دقیقاً چیست؟
  2. Big O: زبان مشترک برای سنجش سرعت
  3. ساختارهای خطی: لیست، پشته و صف
  4. جدول هش: جست‌وجو در زمان ثابت
  5. ساختارهای غیرخطی: درخت، هیپ و گراف
  6. الگوریتم‌های پایه: جست‌وجو، مرتب‌سازی و بازگشت
  7. اشتباهات رایج در کار با داده
  8. کدام ساختمان داده را انتخاب کنیم؟
  9. مسیر یادگیری پیشنهادی

ساختمان داده و الگوریتم دو ستون اصلی علوم کامپیوترند: ساختمان داده تعیین می‌کند داده‌ها چطور در حافظه چیده شوند و الگوریتم می‌گوید روی آن‌ها چه قدم‌هایی برداشته شود. انتخاب درست این دو می‌تواند زمان اجرای یک برنامه را از چند ساعت به چند ثانیه برساند. در این مطلب مفاهیم اصلی را به زبان ساده و با مثال‌های قابل‌اجرای پایتون مرور می‌کنیم.

ساختمان داده و الگوریتم دقیقاً چیست؟

ساختمان داده (Data Structure) قالبی برای نگهداری و سازمان‌دهی داده است؛ مثل قفسه‌بندی یک کتابخانه. الگوریتم (Algorithm) دنباله‌ای مشخص از قدم‌ها برای حل یک مسئله است؛ مثل روش پیدا کردن یک کتاب در همان کتابخانه.

این دو از هم جدا نیستند. اگر کتاب‌ها بر اساس حروف الفبا چیده شده باشند، می‌توانید با روشی سریع مستقیم سراغ قفسه‌ی درست بروید. اگر درهم باشند، چاره‌ای جز نگاه کردن به تک‌تک کتاب‌ها ندارید. در کد هم همین است: ساختمان داده‌ی مناسب، الگوریتم سریع را ممکن می‌کند.

Big O: زبان مشترک برای سنجش سرعت

نماد Big O (Big O Notation) نشان می‌دهد وقتی اندازه‌ی ورودی (n) بزرگ می‌شود، تعداد قدم‌های الگوریتم با چه نرخی رشد می‌کند. این نماد ضرایب ثابت را کنار می‌گذارد و فقط روند رشد را می‌سنجد.

پیچیدگی نام مثال قدم‌ها برای یک میلیون داده (تقریبی)
O(1) ثابت خواندن یک کلید از دیکشنری ۱
O(log n) لگاریتمی جست‌وجوی دودویی حدود ۲۰
O(n) خطی پیمایش یک لیست یک میلیون
O(n log n) خطی‌لگاریتمی مرتب‌سازی کارآمد حدود ۲۰ میلیون
O(n²) درجه‌دو دو حلقه‌ی تودرتو روی همان داده هزار میلیارد

فاصله‌ی ردیف آخر با بقیه نشان می‌دهد چرا یک حلقه‌ی تودرتوی بی‌دقت، روی داده‌ی واقعی می‌تواند سرعت کل سرویس را پایین بیاورد.

Big O فقط درباره‌ی زمان نیست. پیچیدگی حافظه (Space Complexity) هم به همین شکل سنجیده می‌شود: الگوریتمی که برای هر عنصر ورودی یک کپی می‌سازد، حافظه‌ی O(n) مصرف می‌کند. در عمل بیشتر تصمیم‌ها معامله‌ای بین این دو است؛ گاهی کمی حافظه‌ی بیشتر می‌دهید تا زمان را چند مرتبه کمتر کنید. معمولاً بدترین حالت (Worst Case) را گزارش می‌کنند، مگر اینکه صریحاً از حالت میانگین حرف زده شود.

ساختارهای خطی: لیست، پشته و صف

آرایه و لیست

آرایه (Array) عناصر را پشت سر هم در حافظه نگه می‌دارد، پس دسترسی با اندیس فوری است. list در پایتون یک آرایه‌ی پویا است. طبق جدول پیچیدگی ویکی رسمی پایتون، افزودن به انتهای لیست به‌طور میانگین O(1) است، اما درج یا حذف از ابتدای آن O(n)، چون بقیه‌ی عناصر باید جابه‌جا شوند. جست‌وجوی یک مقدار با in هم در لیست O(n) است.

لیست پیوندی (Linked List) برعکس، هر عنصر را جدا ذخیره می‌کند و به عنصر بعدی اشاره می‌دهد. درج در ابتدا سریع است، اما برای رسیدن به عنصر صدم باید صد قدم بروید.

پشته

پشته (Stack) آخرین عنصر واردشده را اول بیرون می‌دهد (LIFO). دکمه‌ی Undo ویرایشگرها و پشته‌ی فراخوانی توابع دو مثال آشنا هستند. لیست پایتون با append و pop یک پشته‌ی کامل است. این تابع بررسی می‌کند پرانتزهای یک عبارت درست باز و بسته شده‌اند:

def is_balanced(text):
    pairs = {")": "(", "]": "[", "}": "{"}
    stack = []
    for ch in text:
        if ch in "([{":
            stack.append(ch)
        elif ch in pairs:
            if not stack or stack.pop() != pairs[ch]:
                return False
    return not stack


print(is_balanced("fn(a[0], {b: 1})"))  # True
print(is_balanced("(]"))                # False

صف

صف (Queue) اولین عنصر واردشده را اول بیرون می‌دهد (FIFO)؛ مثل صف پردازش سفارش‌ها یا پیام‌ها. مستندات رسمی پایتون صریحاً می‌گوید لیست برای صف کارآمد نیست و collections.deque را پیشنهاد می‌کند که افزودن و برداشتن از هر دو سر را سریع انجام می‌دهد:

from collections import deque

queue = deque(["order-1", "order-2"])
queue.append("order-3")
print(queue.popleft())   # order-1

جدول هش: جست‌وجو در زمان ثابت

جدول هش (Hash Table) با یک تابع هش، هر کلید را مستقیم به محل ذخیره‌اش نگاشت می‌کند. dict و set پایتون جدول هش هستند و جست‌وجو، افزودن و حذف در آن‌ها به‌طور میانگین O(1) است.

یک مسئله‌ی کلاسیک: آیا در لیست، دو عدد وجود دارد که جمعشان برابر مقدار هدف باشد؟ راه‌حل ساده دو حلقه‌ی تودرتو است:

def has_pair_with_sum_slow(numbers, target):
    for i in range(len(numbers)):
        for j in range(i + 1, len(numbers)):
            if numbers[i] + numbers[j] == target:
                return True
    return False

این نسخه O(n²) است. با یک set که اعداد دیده‌شده را به خاطر می‌سپارد، همان کار با یک پیمایش یعنی O(n) انجام می‌شود:

def has_pair_with_sum(numbers, target):
    seen = set()
    for n in numbers:
        if target - n in seen:
            return True
        seen.add(n)
    return False


print(has_pair_with_sum([3, 8, 11, 5], 16))  # True (11 + 5)

این الگو، یعنی معامله‌ی کمی حافظه‌ی بیشتر با سرعت بسیار بیشتر، در کد واقعی مدام تکرار می‌شود.

ساختارهای غیرخطی: درخت، هیپ و گراف

درخت

درخت (Tree) داده‌ی سلسله‌مراتبی را نشان می‌دهد: سیستم فایل، ساختار DOM در مرورگر یا نمودار سازمانی. در درخت جست‌وجوی دودویی (Binary Search Tree) هر گره فرزند کوچک‌تر را در چپ و بزرگ‌تر را در راست دارد، پس در درخت متوازن جست‌وجو O(log n) است. ایندکس‌های پایگاه داده هم معمولاً روی خانواده‌ای از درخت‌های متوازن مثل B-tree ساخته می‌شوند.

هیپ و صف اولویت

هیپ (Heap) درختی است که همیشه کوچک‌ترین عنصر (در هیپ کمینه یا Min-Heap) یا بزرگ‌ترین عنصر (در هیپ بیشینه یا Max-Heap) را در ریشه‌اش نگه می‌دارد. ماژول heapq پایتون به‌طور پیش‌فرض یک هیپ کمینه روی لیست معمولی پیاده می‌کند و برای صف اولویت (Priority Queue) عالی است:

import heapq

tasks = []
heapq.heappush(tasks, (2, "review PR"))
heapq.heappush(tasks, (1, "fix production bug"))
heapq.heappush(tasks, (3, "update docs"))
print(heapq.heappop(tasks))   # (1, 'fix production bug')

response_times = [120, 340, 95, 870, 410, 1500, 60]
print(heapq.nlargest(3, response_times))   # [1500, 870, 410]

گراف و جست‌وجوی سطح‌به‌سطح

گراف (Graph) مجموعه‌ای از گره‌ها و یال‌هاست: شبکه‌ی جاده‌ها، دنبال‌کننده‌های یک شبکه‌ی اجتماعی یا وابستگی‌های بسته‌های نرم‌افزاری. الگوریتم جست‌وجوی سطح‌به‌سطح (BFS) با کمک یک صف، کوتاه‌ترین مسیر را از نظر تعداد یال در گراف بدون وزن پیدا می‌کند:

from collections import deque


def shortest_path(graph, start, goal):
    """Breadth-first search: fewest hops from start to goal."""
    queue = deque([[start]])
    visited = {start}
    while queue:
        path = queue.popleft()
        node = path[-1]
        if node == goal:
            return path
        for neighbor in graph.get(node, []):
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(path + [neighbor])
    return None


graph = {
    "Tehran": ["Qom", "Karaj", "Semnan"],
    "Karaj": ["Qazvin"],
    "Qom": ["Kashan"],
    "Kashan": ["Isfahan"],
    "Qazvin": ["Zanjan"],
}
print(shortest_path(graph, "Tehran", "Isfahan"))
# ['Tehran', 'Qom', 'Kashan', 'Isfahan']

دقت کنید که اینجا هر سه ساختار کنار هم کار می‌کنند: دیکشنری برای گراف، deque برای صف و set برای گره‌های دیده‌شده.

الگوریتم‌های پایه: جست‌وجو، مرتب‌سازی و بازگشت

جست‌وجوی دودویی

اگر لیست مرتب باشد، لازم نیست همه‌ی عناصر را ببینید. جست‌وجوی دودویی (Binary Search) هر بار عنصر وسط را بررسی می‌کند و نیمی از فضا را کنار می‌گذارد؛ یعنی O(log n):

def binary_search(items, target):
    """Return the index of target in a sorted list, or -1."""
    low, high = 0, len(items) - 1
    while low <= high:
        mid = (low + high) // 2
        if items[mid] == target:
            return mid
        if items[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return -1


prices = [12, 19, 25, 31, 44, 58, 73]
print(binary_search(prices, 44))   # 4

در کد واقعی از ماژول استاندارد bisect استفاده کنید؛ bisect_left محل درج یک مقدار را در لیست مرتب برمی‌گرداند و با آن می‌توانید وجود مقدار را هم بررسی کنید.

مرتب‌سازی

الگوریتم‌های مرتب‌سازی کارآمد مثل مرتب‌سازی ادغامی (Merge Sort) در O(n log n) کار می‌کنند. یاد گرفتن ایده‌ی آن‌ها ذهن الگوریتمی را قوی می‌کند، اما در کد روزمره از sorted() یا list.sort() پایتون استفاده کنید که بهینه و پایدار (Stable) است؛ یعنی ترتیب نسبی عناصر برابر را حفظ می‌کند.

بازگشت: تابعی که خودش را صدا می‌زند

بسیاری از الگوریتم‌های درخت و گراف با بازگشت (Recursion) ساده‌تر نوشته می‌شوند. تابع بازگشتی مسئله را به نسخه‌ی کوچک‌تری از همان مسئله می‌شکند و یک حالت پایه (Base Case) دارد که بازگشت را متوقف می‌کند. این تابع تعداد فایل‌های یک ساختار پوشه‌ی تودرتو را می‌شمارد؛ پوشه‌ها دیکشنری‌اند و فایل‌ها None:

def count_files(tree):
    total = 0
    for child in tree.values():
        total += 1 if child is None else count_files(child)
    return total


project = {"src": {"main.py": None, "utils": {"io.py": None}}, "README.md": None}
print(count_files(project))   # 3

پایتون عمق بازگشت را محدود می‌کند، پس برای ساختارهای خیلی عمیق نسخه‌ی تکراری با یک پشته‌ی دستی امن‌تر است.

اشتباهات رایج در کار با داده

  • جست‌وجو در لیست داخل حلقه: عبارت if x in big_list درون یک حلقه، بی‌صدا O(n²) می‌سازد. لیست را یک بار به set تبدیل کنید.
  • pop(0) روی لیست بزرگ: برای صف از deque.popleft() استفاده کنید.
  • مرتب‌سازی دوباره در هر تکرار: اگر فقط چند عنصر بزرگ لازم دارید، heapq.nlargest سریع‌تر است.
  • بهینه‌سازی زودهنگام: برای ده عنصر، ساده‌ترین کد بهترین کد است. اول اندازه بگیرید، بعد بهینه کنید.

کدام ساختمان داده را انتخاب کنیم؟

نیاز ساختار مناسب در پایتون
دسترسی با اندیس و پیمایش ترتیبی list
بررسی سریع «وجود دارد یا نه» set
نگاشت کلید به مقدار dict
صف یا افزودن و برداشتن از دو سر collections.deque
همیشه کوچک‌ترین یا مهم‌ترین عنصر heapq
جست‌وجو در داده‌ی مرتب bisect

مسیر یادگیری پیشنهادی

  1. Big O را با تحلیل کدهای خودتان تمرین کنید؛ هر حلقه‌ی تودرتو را ببینید و بپرسید آیا می‌شود حذفش کرد.
  2. لیست، دیکشنری، مجموعه و deque را عمیق بشناسید؛ بیشتر مسائل روزمره با همین‌ها حل می‌شود.
  3. درخت، هیپ و گراف را با پیاده‌سازی BFS و DFS یاد بگیرید.
  4. مسائل تمرینی را دسته‌بندی‌شده حل کنید و بعد از حل هر مسئله، پیچیدگی زمانی و حافظه‌ی راه‌حلتان را بنویسید. این همان مهارتی است که در مصاحبه‌ی فنی سنجیده می‌شود؛ راهنمای مصاحبه‌ی برنامه‌نویسی مسیر آماده شدن برای آن را توضیح می‌دهد.

اگر هنوز با خود پایتون راحت نیستید، از آموزش پایتون از صفر شروع کنید. و وقتی راه‌حل سریع را پیدا کردید، فراموش نکنید که خوانا هم بنویسیدش؛ اصول کلین کد دقیقاً برای همین لحظه است.

$ devna rate --article

—
هنوز رأیی ثبت نشده
  1. ۵۰
  2. ۴۰
  3. ۳۰
  4. ۲۰
  5. ۱۰

این مطلب چقدر به کارتان آمد؟

روی ستاره‌ها بزنید

واکنش شما

اولین نفری باشید که واکنش نشان می‌دهد.

پرسش‌های پرتکرار

برای کار واقعی هم ساختمان داده و الگوریتم لازم است یا فقط برای مصاحبه؟

هر دو. در کار روزمره کمتر پیش می‌آید که الگوریتم را از صفر بنویسید، اما انتخاب بین لیست، دیکشنری و مجموعه یا تشخیص یک حلقه‌ی تودرتوی کند، مستقیم روی سرعت و هزینه‌ی سرویس اثر می‌گذارد.

Big O چیست و چه چیزی را اندازه می‌گیرد؟

Big O نشان می‌دهد با بزرگ شدن ورودی، زمان اجرا یا حافظه با چه نرخی رشد می‌کند. زمان دقیق را بر حسب ثانیه نمی‌گوید و ضرایب ثابت را نادیده می‌گیرد.

بهترین زبان برای یادگیری ساختمان داده و الگوریتم چیست؟

مفاهیم مستقل از زبان‌اند. پایتون به‌خاطر خوانایی برای شروع مناسب است؛ زبان‌هایی مثل C یا Go کمک می‌کنند جزئیات حافظه را هم بهتر ببینید.

آیا باید الگوریتم‌های مرتب‌سازی را حفظ کنم؟

حفظ کردن لازم نیست. کافی است ایده‌ی چند روش، مثل مرتب‌سازی ادغامی (Merge Sort) و مرتب‌سازی سریع (Quick Sort)، و پیچیدگی زمانی‌شان را بفهمید. در کد واقعی از تابع مرتب‌سازی آماده‌ی زبان استفاده کنید.

منابع

  1. Python Tutorial – Data Structures
  2. Python Wiki – TimeComplexity
  3. heapq — Heap queue algorithm
  4. bisect — Array bisection algorithm

خطایی در این مطلب دیدید؟ به تحریریه گزارش دهید؛ اصلاحیه‌ها طبق اصول تحریریه ثبت می‌شوند.

دیدگاه‌ها

۰/۲٬۰۰۰

دیدگاه‌ها پس از بررسی تحریریه منتشر می‌شوند. توهین، تبلیغ و لینک‌های بی‌ربط حذف می‌شوند؛ نقد فنی و مستند همیشه خوش‌آمد است.

$ comments --count۰

هنوز کسی چیزی ننوشته. اولین دیدگاه را شما ثبت کنید.

مطالب مرتبط