تصویر شاخص نوشته: الگوریتم چیست؟ تعریف ساده، مثال واقعی و اینکه از کجا بفهمیم یک الگوریتم خوب است

الگوریتم چیست؟ تعریف ساده، مثال واقعی و اینکه از کجا بفهمیم یک الگوریتم خوب است

۲۸ آبان ۱۴۰۵ مبانی برنامه‌نویسی

الگوریتم دنباله‌ای از قدم‌های دقیق و متناهی است که از یک ورودی، یک خروجی درست می‌سازد. «دقیق» یعنی هر قدم فقط یک معنی دارد و یک ماشین بی‌فکر هم می‌تواند انجامش بدهد. «متناهی» یعنی کار بالاخره تمام می‌شود. دستور پخت غذا نزدیک‌ترین مثال روزمره است، به شرطی که «کمی نمک» را با «پنج گرم نمک» عوض کنی.

الگوریتم، برنامه و ساختمان داده

این سه را معمولاً با هم قاطی می‌کنند:

مفهوم چیست مثال
الگوریتم ایدهٔ قدم‌به‌قدم حل مسئله، مستقل از زبان «وسط را نگاه کن و نصف بی‌فایده را دور بریز»
برنامه همان ایده، نوشته‌شده در یک زبان مشخص تابع binary_search در پایتون
ساختمان داده شکل نگه‌داشتن داده در حافظه فهرست مرتب‌شده‌ای که الگوریتم رویش کار می‌کند

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

پنج ویژگی یک الگوریتم

دونالد کنوت در کتاب «هنر برنامه‌نویسی کامپیوتر» پنج ویژگی برای الگوریتم می‌شمارد. خلاصه‌اش این است:

  1. متناهی‌بودن: بعد از تعداد محدودی قدم تمام می‌شود.
  2. دقیق‌بودن: هر قدم دقیق و بدون ابهام تعریف شده است.
  3. ورودی: صفر یا چند ورودی دارد.
  4. خروجی: دست‌کم یک خروجی دارد که به ورودی ربط دارد.
  5. اجراپذیری: هر قدم آن‌قدر ساده است که بشود واقعاً انجامش داد.

دستور «تا وقتی هوا خوب است قدم بزن» الگوریتم نیست، چون معلوم نیست تمام شود و «خوب» هم دقیق نیست.

یک مثال کامل: جست‌وجوی دودویی

فرض کن یک فهرست مرتب از یک میلیون عدد داری و می‌خواهی بدانی عددی در آن هست یا نه. راه ساده این است که از اول تک‌تک نگاه کنی. اسمش جست‌وجوی خطی است و در بدترین حالت یک میلیون قدم می‌خواهد.

راه دیگر جست‌وجوی دودویی است: عضو وسط را نگاه کن. اگر هدف بزرگ‌تر است، نیمهٔ چپ را کنار بگذار. اگر کوچک‌تر است، نیمهٔ راست را. همین را تکرار کن تا پیدا شود یا بازه خالی شود.

import math

def binary_search(values, target):
    """Return (index or -1, number of steps)."""
    lo, hi = 0, len(values) - 1
    steps = 0
    while lo <= hi:
        steps += 1
        mid = (lo + hi) // 2
        if values[mid] == target:
            return mid, steps
        if values[mid] < target:
            lo = mid + 1      # target can only be to the right
        else:
            hi = mid - 1      # target can only be to the left
    return -1, steps

n = 1_000_000
values = list(range(0, 2 * n, 2))      # sorted even numbers
worst = max(binary_search(values, v)[1] for v in values)
print("log2(n):", round(math.log2(n), 2))
print("worst steps, found:", worst)
print("steps, missing:", binary_search(values, 7)[1])
log2(n): 19.93
worst steps, found: 20
steps, missing: 20

یک میلیون عضو، حداکثر ۲۰ قدم. دلیلش این است که هر قدم بازه را نصف می‌کند، و یک میلیون را حدود ۲۰ بار می‌شود نصف کرد تا به یک برسد: log₂(1,000,000) ≈ 19.93. کد بالا این را روی همهٔ یک میلیون عضو آزموده است، نه فقط روی یک نمونه.

چیزی که این الگوریتم را درست نگه می‌دارد یک جمله است: «اگر هدف در فهرست باشد، حتماً بین lo و hi است.» این جمله قبل از شروع درست است و در هر دور درست می‌ماند، چون فقط نیمه‌ای دور ریخته می‌شود که ثابت شده هدف در آن نیست. به چنین جمله‌ای ناوردا (invariant) می‌گویند.

الگوریتم ساده هم می‌تواند بی‌صدا غلط باشد

جست‌وجوی دودویی از مشهورترین الگوریتم‌هایی است که برنامه‌نویس‌ها غلط می‌نویسند. در فصل جست‌وجوی دودویی بنیاد، فقط با عوض‌کردن <= به < در شرط حلقه، تابع برای ۴۸۹ عضو از ۱٬۰۰۰ عضوی که واقعاً در فهرست بودند جواب «پیدا نشد» داد. هیچ خطا یا هشداری هم نداد.

درس این مثال این است که درستی یک الگوریتم را با یکی دو امتحان دستی نمی‌شود ثابت کرد. یا باید استدلال کنی (مثل ناوردای بالا)، یا همهٔ حالت‌ها را بیازمایی، و بهتر است هر دو را انجام بدهی. در کار واقعی پایتون هم ماژول bisect همین الگوریتم را آماده دارد و لازم نیست خودت بنویسی‌اش.

یک الگوریتم خوب را چطور قضاوت کنیم

این سؤال‌ها را به ترتیب بپرس:

  1. درست است؟ برای همهٔ ورودی‌ها، از جمله فهرست خالی، یک‌عضوی و عضوی که نیست؟
  2. تمام می‌شود؟ حلقه‌ای که بازه‌اش کوچک نمی‌شود، هیچ‌وقت تمام نمی‌شود.
  3. با بزرگ‌شدن داده چطور رشد می‌کند؟ این همان چیزی است که Big O اندازه می‌گیرد.
  4. چه پیش‌شرطی دارد و آن پیش‌شرط چقدر خرج دارد؟
  5. چقدر حافظه می‌خواهد؟
  6. آدم دیگری می‌تواند بخواند و درستی‌اش را بسنجد؟

سؤال سوم همان جایی است که «درست» و «قابل‌استفاده» از هم جدا می‌شوند. فصل اول بنیاد تابعی شش‌خطی دارد که دنبال کد تکراری می‌گردد. روی هشت هزار عدد کمی بیش از یک ثانیه طول می‌کشد و روی هشتصد هزار عدد حدود سه ساعت. باگی در کار نیست و جواب همیشه درست است، ولی روی دادهٔ بزرگ قابل‌استفاده نیست.

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

پیش‌شرط رایگان نیست

جست‌وجوی دودویی سریع است، ولی فقط روی دادهٔ مرتب کار می‌کند و مرتب‌کردن خودش هزینه دارد. پس سؤال واقعی این است: چند بار می‌خواهی جست‌وجو کنی؟

اگر فقط یک بار می‌پرسی، یک جست‌وجوی خطی ارزان‌تر از «اول مرتب کن، بعد جست‌وجوی دودویی» است. اگر بارها می‌پرسی، هزینهٔ یک‌بارهٔ مرتب‌کردن بین همهٔ پرسش‌ها تقسیم می‌شود. در شمارش فصل جست‌وجوی دودویی بنیاد، با هشت هزار عضو، از ۲۴ پرسش به بعد مرتب‌کردن به‌صرفه شد. این عدد به n و به نوع داده بستگی دارد، و نکته همین است: الگوریتم خوب بدون دانستن الگوی استفاده معنی ندارد.

چند الگوریتم آشنا

الگوریتم چه می‌کند رشد تقریبی
پیداکردن بزرگ‌ترین عضو یک بار همه را نگاه می‌کند O(n)
جست‌وجوی خطی از اول تا پیداشدن O(n)
جست‌وجوی دودویی روی دادهٔ مرتب، نصف‌کردن بازه O(log n)
مرتب‌سازی ادغامی (merge sort) نصف کن، هر نیمه را مرتب کن، ادغام کن O(n log n)
مقایسهٔ هر جفت دو حلقهٔ تودرتو O(n²)

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

اگر می‌خواهی این موضوع را کامل یاد بگیری

خودآموز بنیاد

ساختمان داده و الگوریتم، با اندازه‌گیری واقعی

ساختمان داده و الگوریتم را با پایتون یاد بگیر، با اندازه‌گیری به‌جای حفظ‌کردن. کدت درست کار می‌کند و روی دادهٔ واقعی غیرقابلِ استفاده است. این دوره می‌گوید چرا — و مهم‌تر، چطور قبل از اجرا پیش‌بینی‌اش کنی: اندازه‌گیریِ صادقانهٔ زمان، Big-O به‌عنوان یک پیش‌بینی که آزمون می‌دهد، list و hash و درخت و گراف، مرتب‌سازی و جست‌وجو، و یک قاعدهٔ سخت — هیچ ادعای پیچیدگی بدونِ جدولِ اندازه‌گیری. همه در Google Colab، فقط روی CPU و فقط با کتابخانهٔ استاندارد.

  • ۶ ترم
  • ۴۹ فصل
  • همهٔ فصل‌ها رایگان

برای خواندن بدون اینترنت

خودآموز دانلودی بنیاد

PDF، EPUB، MOBI · ۸۲۴ صفحه

۲۹۹٬۰۰۰ تومان

دیدن نسخهٔ دانلودی