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

فهرست مطالب
ساختمان داده و الگوریتم دو ستون اصلی علوم کامپیوترند: ساختمان داده تعیین میکند دادهها چطور در حافظه چیده شوند و الگوریتم میگوید روی آنها چه قدمهایی برداشته شود. انتخاب درست این دو میتواند زمان اجرای یک برنامه را از چند ساعت به چند ثانیه برساند. در این مطلب مفاهیم اصلی را به زبان ساده و با مثالهای قابلاجرای پایتون مرور میکنیم.
ساختمان داده و الگوریتم دقیقاً چیست؟
ساختمان داده (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 |
مسیر یادگیری پیشنهادی
- Big O را با تحلیل کدهای خودتان تمرین کنید؛ هر حلقهی تودرتو را ببینید و بپرسید آیا میشود حذفش کرد.
- لیست، دیکشنری، مجموعه و
dequeرا عمیق بشناسید؛ بیشتر مسائل روزمره با همینها حل میشود. - درخت، هیپ و گراف را با پیادهسازی BFS و DFS یاد بگیرید.
- مسائل تمرینی را دستهبندیشده حل کنید و بعد از حل هر مسئله، پیچیدگی زمانی و حافظهی راهحلتان را بنویسید. این همان مهارتی است که در مصاحبهی فنی سنجیده میشود؛ راهنمای مصاحبهی برنامهنویسی مسیر آماده شدن برای آن را توضیح میدهد.
اگر هنوز با خود پایتون راحت نیستید، از آموزش پایتون از صفر شروع کنید. و وقتی راهحل سریع را پیدا کردید، فراموش نکنید که خوانا هم بنویسیدش؛ اصول کلین کد دقیقاً برای همین لحظه است.




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