الگوریتم‌ها
فهرست الگوریتم‌ها بر اساس موضوع. الگوریتم‌های بیشتر به‌تدریج اضافه می‌شوند.
گراف
↑ همه‌ی موضوعهاپیمایش گراف
- نقاط مفصلیگره‌هایی را پیدا می‌کند که با حذفشان گراف تکه می‌شود؛ با یک DFS و مقدار low هر گره (کمترین زمان کشفی که از زیردرختش قابل دسترس است).زمان:
O(V + E) - جستجوی اول سطح (BFS)گراف را لایه‌به‌لایه از مبدأ پیمایش می‌کند و کمترین تعداد یال تا هر گره را با یک صف پیدا می‌کند.زمان:
O(V + E) - چندجمله‌ای رنگیتعداد رنگ‌آمیزی‌های درست یک گراف با k رنگ را به صورت چندجمله‌ای در k پیدا می‌کند، با قاعده‌ی حذف و ادغام: P(G) = P(G − e) − P(G / e). زمان نمایی در تعداد یال‌ها.زمان:
O(2^m · (n + m)) - مؤلفه‌های همبندگره‌های گراف بی‌جهت را بر اساس اینکه به هم راه دارند گروه‌بندی می‌کند: از هر گره‌ی برچسب‌نخورده یک پیمایش تازه شروع می‌شود.زمان:
O(V + E) - جستجوی اول عمق (DFS)از مبدأ تا جایی که می‌شود در یک مسیر جلو می‌رود و وقتی به بن‌بست رسید، برمی‌گردد و راه دیگری را امتحان می‌کند.زمان:
O(V + E) - دور اویلری (هیرهولتسر)دوری پیدا می‌کند که از هر یال دقیقاً یک بار می‌گذرد؛ هر جا گیر کرد، یک دور فرعی را در مسیر جا می‌دهد.زمان:
O(V + E) - رنگ‌آمیزی حریصانه‌ی گرافگره‌ها را به ترتیب درجه (ولش–پاول) برمی‌دارد و به هر کدام کوچک‌ترین رنگی را می‌دهد که همسایه‌هایش ندارند.زمان:
O(V log V + E) - یکریختی گراف (پس‌گرد)دنبال نگاشتی از رأس‌های یک گراف به دیگری می‌گردد که همه‌ی یال‌ها و نایال‌ها را حفظ کند: رأس به رأس، با پس‌گرد و هرس با درجه‌ها. در بدترین حالت n! حالت.زمان:
O(n! · n) in the worst case - دور همیلتونی (عقبگرد)دوری را جست‌وجو می‌کند که از هر گره دقیقاً یک بار می‌گذرد؛ مسیر را گره‌به‌گره بلند می‌کند و در بن‌بست عقب برمی‌گردد.زمان:
O(V!) - مؤلفه‌های قویاً همبندگراف جهت‌دار را به گروه‌هایی تقسیم می‌کند که در هر کدام از هر گره به هر گره‌ی دیگر راه هست؛ با دو DFS (الگوریتم کوساراجو).زمان:
O(V + E) - مرتب‌سازی توپولوژیکگره‌های گراف جهت‌دار بی‌دور را طوری می‌چیند که هر یال از گره‌ی قبلی به بعدی برود؛ مثل ترتیب گذراندن درس‌ها با پیش‌نیاز.زمان:
O(V + E) - بستار تراگذری (وارشال)برای هر جفت گره تعیین می‌کند آیا از اولی به دومی راهی هست؛ مثل فلوید–وارشال ولی با «یا» و «و» به جای کمینه و جمع.زمان:
O(V³) - مجموعه‌های مجزا (Union-Find)یال‌ها را یکی‌یکی می‌خواند و مجموعه‌ی دو سرشان را یکی می‌کند؛ با «ادغام بر اساس رتبه» و «فشرده‌سازی مسیر» هر عمل تقریباً O(1) است.زمان:
O(E · α(V)) - پوشش رأسی تقریبیهر یالی که هنوز پوشیده نشده، هر دو سرش را برمی‌دارد؛ جواب حداکثر دو برابر بهینه است.زمان:
O(V + E)
کوتاه‌ترین مسیر
- الگوریتم بلمن–فوردکوتاهترین مسیر از مبدأ حتی با یالهای منفی: همه‌ی یال‌ها را V − 1 بار relax می‌کند و دور منفی را هم تشخیص می‌دهد.زمان:
O(V · E) - مسیر بحرانی (شبکهی AOE)در شبکهی فعالیتها، زودترین و دیرترین زمان هر رویداد را حساب می‌کند و فعالیتهایی را پیدا می‌کند که هیچ تأخیری نمیپذیرند.زمان:
O(V + E) - کوتاه‌ترین مسیر در گراف بیدوردر گراف جهت‌دار بی‌دور، گرهها را به ترتیب توپولوژیک یک بار relax می‌کند؛ با یال منفی هم کار می‌کند و از Dijkstra هم سریعتر است.زمان:
O(V + E) - قیدهای تفاضلیدستگاهی از نامعادلههای x_j − x_i ≤ b را به گرافی تبدیل می‌کند و با بلمن–فورد حل می‌کند: فاصلههای کوتاه‌ترین مسیر یک جواباند، و دور منفی یعنی دستگاه جواب ندارد.زمان:
O(n · m) - الگوریتم دایکستراکوتاهترین فاصله از یک گره‌ی مبدأ تا همه‌ی گرههای یک گراف با وزنهای نامنفی، با یک صف اولویت.زمان:
O((V + E) log V) - الگوریتم فلوید–وارشالکوتاهترین مسیر بین همه‌ی جفت گرهها با برنامه‌ریزی پویا: گرهها یکی‌یکی بهعنوان ایستگاه میانی مجاز می‌شوند.زمان:
O(V³) - الگوریتم جانسونکوتاهترین مسیر همه‌ی جفتها با یال منفی: با بلمن–فورد وزنها را نامنفی می‌کند و بعد از هر گره Dijkstra اجرا می‌کند.زمان:
O(V · E log V) - کوتاه‌ترین مسیر همه‌ی جفتها با مربعسازی مکررکوتاهترین مسیر بین همه‌ی جفتها را با «ضرب» ماتریس وزنها در خودش پیدا می‌کند، با min به جای جمع و + به جای ضرب؛ با مربع کردن مکرر، log n ضرب کافی است. Θ(n³ log n).زمان:
Θ(n³ log n)
درخت پوشای کمینه
- فروشندهی دورهگرد تقریبیدرخت پوشای کمینه میسازد و گرهها را به ترتیب پیشترتیب درخت میپیماید؛ اگر نامساوی مثلث برقرار باشد، تور حداکثر دو برابر بهینه است.زمان:
O(V²) - الگوریتم بروفکا (سولین)در هر دور، هر مؤلفه سبکترین یالِ بیرونروندهاش را برمی‌دارد؛ تعداد مؤلفهها هر دور دستکم نصف می‌شود.زمان:
O(E log V) - الگوریتم کروسکالیالها را از سبک به سنگین مرور می‌کند و هر یالی را که دور نمیسازد به درخت پوشای کمینه اضافه می‌کند.زمان:
O(E log E) - الگوریتم پریمدرخت پوشای کمینه را از یک گره رشد می‌دهد: هر بار سبکترین یالی را که گرهای تازه را به درخت وصل می‌کند اضافه می‌کند.زمان:
O((V + E) log V)
جریان شبکه و تطابق
- تطابق بیشینه در گراف دوبخشیهر گره‌ی سمت چپ را با یک مسیر افزایشی جفت می‌کند؛ اگر همسایهاش گرفته باشد، جفت قبلی را به همسایهی دیگری منتقل می‌کند.زمان:
O(V · E) - الگوریتم گیل–شپلی (ازدواج پایدار)مردان به ترتیب علاقه خواستگاری می‌کنند و زنان همیشه بهترین پیشنهاد تا آن لحظه را نگه میدارند؛ نتیجه یک جورسازی پایدار است: هیچ دو نفری نیستند که همدیگر را به همسرشان ترجیح دهند. حداکثر n² خواستگاری.زمان:
O(n²) - الگوریتم هاپکرافت–کارپتطابق بیشینه در گراف دوبخشی با فازها: در هر فاز با BFS لایه میسازد و بعد چند مسیر افزایشی کوتاه و جدا از هم را با DFS پیدا می‌کند.زمان:
O(E √V) - الگوریتم مجارستانی (تخصیص بهینه)هر کارگر را به یک کار متفاوت با کمترین هزینهی کل می‌دهد: تطابق را فقط روی خانههای صفرِ ماتریس کاهشیافته میسازد و هر جا گیر کرد، صفر تازه میسازد.زمان:
O(n⁴) here (O(n³) with more bookkeeping) - بیشینهی جریان (ادموندز–کارپ)تا وقتی در شبکهی باقیمانده مسیری از مبدأ به آخرین گره هست، کوتاهترینش را با BFS پیدا می‌کند و جریان را از آن عبور می‌دهد.زمان:
O(V · E²)
مرتب‌سازی
↑ همه‌ی موضوعهامرتبسازی مقایسه‌ای
- مرتب‌سازی حبابیجفتهای کنار هم را مقایسه و در صورت نیاز جابهجا می‌کند؛ در هر گذر، بزرگترین عضو مثل حباب به انتها می‌رود.زمان:
O(n²), O(n) if already sorted - مرتب‌سازی هرمیآرایه را به یک هرم بیشینه تبدیل می‌کند و بعد بارها بزرگترین عضو را از ریشه برمی‌دارد و به انتهای آرایه میبرد.زمان:
O(n log n) - افراز هوردو اشارهگر از دو سر آرایه به هم نزدیک می‌شوند و عضوهای نابهجا را جابهجا می‌کنند تا آرایه به دو بخش ≤ محور و ≥ محور تقسیم شود.زمان:
O(n) - مرتب‌سازی درجیمثل مرتب کردن کارتهای بازی در دست: هر عضو را برمی‌دارد و در جای درستش در بخش مرتبشدهی سمت چپ میگذارد.زمان:
O(n²) - ادغام k-راههk دنبالهی مرتب را با یک هیپ کمینه همزمان ادغام می‌کند: هر بار کوچکترینِ سرِ دنبالهها را برمی‌دارد. پایهی مرتب‌سازی خارجی.زمان:
O(n log k) - مرتب‌سازی ادغامیآرایه را از وسط دو نیم می‌کند، هر نیمه را بهصورت بازگشتی مرتب می‌کند و دو نیمهی مرتب را در هم ادغام می‌کند.زمان:
O(n log n) - صف اولویت با هرمدرج در هرم بیشینه با بالا بردن عضو تازه، و برداشتن بیشینه با پایین بردن عضوی که جای ریشه نشسته؛ هر دو O(log n).زمان:
O(log n) per operation - مرتب‌سازی سریعآخرین عضو را محور میگیرد، کوچکترها را به چپ و بزرگترها را به راستش میبرد و هر طرف را بهصورت بازگشتی مرتب می‌کند.زمان:
O(n log n) on average, O(n²) at worst - مرتب‌سازی انتخابیدر هر دور کوچک‌ترین عضو بخش نامرتب را پیدا می‌کند و آن را به ابتدای همان بخش میبرد.زمان:
O(n²) - مرتب‌سازی شلمرتبسازی درجی روی عضوهایی که gap خانه از هم فاصله دارند، با gapهای کوچکشونده تا ۱؛ عضوهای دور زود به جای درستشان نزدیک می‌شوند.زمان:
O(n²) with gaps n/2, n/4, …; better with other gap sequences - مرتب‌سازی جدولیبهجای جابهجا کردن رکوردهای بزرگ، جدولی از اندیسها را مرتب می‌کند و بعد هر رکورد را فقط یک بار، با دنبال کردن دورهای جایگشت، سر جایش میبرد.زمان:
O(n²) comparisons, O(n) record moves
مرتب‌سازی بدون مقایسه
- مرتب‌سازی سطلیبازه را به n سطل برابر تقسیم می‌کند، هر عدد را در سطل خودش میاندازد، سطلها را جدا مرتب می‌کند و پشت هم می‌چیند.زمان:
O(n) on average for evenly spread input, O(n²) at worst - مرتب‌سازی شمارشیبدون مقایسه: میشمارد هر مقدار چند بار آمده و از روی جمعهای پیشوندی، جای هر عضو در خروجی را مستقیم حساب می‌کند.زمان:
O(n + k) - مرتب‌سازی مبناییعددها را رقمبهرقم، از یکان شروع کرده، با یک مرتب‌سازی شمارشی پایدار مرتب می‌کند؛ بعد از آخرین رقم کل آرایه مرتب است.زمان:
O(d·(n + 10)) for d digits
جستجو
↑ همه‌ی موضوعهاجستجو در آرایه
- جستجوی دودوییدر آرایهی مرتب، هر بار عضو وسط بازه را با مقدار مورد جستجو مقایسه می‌کند و نیمی از بازه را کنار میگذارد.زمان:
O(log n) - بُر زدن فیشر–یِیتساز انتها به ابتدا، هر خانه را با خانهای تصادفی از بخش هنوز بُرنخورده جابهجا می‌کند؛ همه‌ی جایگشتها با احتمال برابر به دست میآیند.زمان:
O(n) - مسئلهی استخدامداوطلبها یکی‌یکی میآیند و هر بار که کسی از همه‌ی قبلیها بهتر بود، استخدام می‌شود؛ چند بار استخدام میکنیم؟زمان:
n interviews; about ln n hires on average for a random order - جستجوی درونیابیمثل جستجوی دودویی، ولی بهجای وسط، از روی مقدار target حدس می‌زند کجای بازه باشد؛ مثل پیدا کردن کلمه در فرهنگ لغت.زمان:
O(log log n) for evenly spread data, O(n) at worst - جستجوی خطیعضوها را یکی‌یکی از ابتدا با مقدار مورد جستجو مقایسه می‌کند تا آن را پیدا کند یا آرایه تمام شود.زمان:
O(n) - بیشینهی زیرآرایه (کادان)بازهی پیوستهای با بیشترین مجموع را در یک گذر پیدا می‌کند: هر وقت مجموع جاری منفی شد، آن را کنار میگذارد و از نو شروع می‌کند.زمان:
O(n) - انتخاب با میانهی میانههاk-امین عنصر کوچک را در بدترین حالت هم در زمان خطی پیدا می‌کند: محور، میانهی میانههای گروههای پنجتایی است.زمان:
O(n) - کمینه و بیشینه با همعضوها را جفتجفت برمی‌دارد: کوچکترِ جفت فقط با کمینه و بزرگترش فقط با بیشینه مقایسه می‌شود؛ ۳ مقایسه برای هر ۲ عضو.زمان:
about 3n/2 comparisons - جایگشت بعدیجایگشت بعدی را در ترتیب فرهنگ لغتی درجا میسازد: از انتها اولین افت را پیدا می‌کند، یک جابهجایی و یک وارونهسازی.زمان:
O(n) - انتخاب سریع (k امین کوچک‌ترین)مثل مرتب‌سازی سریع افراز می‌کند، ولی فقط در سمتی که k امین عضو در آن است ادامه می‌دهد؛ بهطور متوسط زمان خطی.زمان:
O(n) on average, O(n²) at worst
درهم‌سازی
- فیلتر بلومعضویت در مجموعه را با یک آرایهی بیتی و چند تابع درهم‌سازی میسنجد: «قطعاً نیست» یا «شاید هست»، با حافظهی خیلی کم.زمان:
O(k) per key for k hash functions - درهم‌سازی توسعهپذیرجدول درهمسازیای که با پر شدن، به جای بازسازی کل جدول فقط یک سطل را دو تا می‌کند و در صورت لزوم فهرست راهنما را دو برابر؛ هر کلید با یک یا دو دسترسی پیدا می‌شود.زمان:
O(1) expected per operation - جدول درهم‌سازی با زنجیرههر خانهی جدول یک لیست است و کلیدهایی که به یک خانه درهم می‌شوند پشت هم در همان لیست میروند؛ برخورد هیچوقت جا را پر نمیکند.زمان:
O(1 + n/m) on average per operation - جدول درهم‌سازی با درهم‌سازی دوگانهمثل کاوش خطی، ولی اندازهی گام را تابع درهم‌سازی دوم از روی خود کلید تعیین می‌کند، پس کلیدهای همخانه مسیرهای متفاوتی میروند.زمان:
O(1) per insert on average when the table is not too full - جدول درهم‌سازی با کاوش خطیهر کلید در خانهی key mod m مینشیند؛ اگر پر بود، خانههای بعدی را یکی‌یکی امتحان می‌کند تا جای خالی پیدا شود.زمان:
O(1) per insert on average when the table is not too full
رشته‌ها
↑ همه‌ی موضوعهاتطبیق رشته
- تطبیق رشته با ماشین حالتبرای الگو یک ماشین حالت متناهی میسازد که حالتش «چقدر از الگو تا اینجا جور شده» است؛ بعد متن را با یک نگاه به جدول برای هر نویسه می‌خواند.زمان:
O(n) to match, after O(m³·|Σ|) to build δ here - الگوریتم KMP (کنوت–موریس–پرات)تطبیق رشته در O(n + m): هیچ نویسهای از متن دوباره خوانده نمیشود؛ بعد از ناهمخوانی، تابع پیشوند میگوید الگو چقدر جلو برود.زمان:
O(n + m) - تابع پیشوند KMPبرای هر پیشوند الگو، طول بلندترین پیشوند سرهای را که پسوند آن هم هست حساب می‌کند؛ KMP با همین جدول بعد از ناهمخوانی میداند چقدر جلو برود.زمان:
O(m) (amortized) - تطبیق رشتهی سادهالگو را زیر هر جای ممکن از متن میگذارد و نویسهبهنویسه مقایسه می‌کند؛ ساده ولی در بدترین حالت O((n − m + 1)·m).زمان:
O((n − m + 1)·m) - الگوریتم رابین–کارپهر پنجرهی متن را عددی به پیمانهی q میبیند و با «درهم‌سازی غلتان» در O(1) بهروزش می‌کند؛ فقط وقتی باقیماندهها برابرند نویسهها را مقایسه می‌کند.زمان:
O(n + m) expected, O((n − m + 1)·m) worst - آرایهی پسوندی و LCPهمه‌ی پسوندهای رشته را مرتب می‌کند و برای هر دو پسوند همسایه طول بلندترین پیشوند مشترک را با روش کاسای در O(n) حساب می‌کند.زمان:
O(n² log n) to sort here (O(n log n) with doubling), O(n) for LCP
عبارت‌ها و پشته
- تطابق پرانتزهابا یک پشته بررسی می‌کند که پرانتزها، کروشهها و آکولادها درست باز و بسته شدهاند: هر بسته باید با آخرین باز همنوع باشد.زمان:
O(n) - تبدیل میانوندی به پسوندیعبارت ریاضی معمولی را با یک پشته به نمادگذاری پسوندی (لهستانی معکوس) میبرد؛ اولویت و پرانتزها با ترتیب خروج عملگرها از پشته رعایت می‌شوند.زمان:
O(n) - محاسبهی عبارت پسوندیعبارت پسوندی را با یک پشته در یک گذر حساب می‌کند: عدد روی پشته می‌رود و هر عملگر دو عدد بالای پشته را برمی‌دارد و حاصل را برمیگرداند.زمان:
O(n)
ماشین‌های حالت
- کمینهسازی DFAحالتهای همارز یک ماشین قطعی را یکی می‌کند: از تقسیم به پذیرش و غیرپذیرش شروع می‌کند و دستهها را تا جایی میشکند که دیگر شکستنی نباشند.زمان:
O(n²) here (O(n log n) with Hopcroft's method) - ماشین حالت متناهی (تشخیص دنباله)یک ماشین سهحالته رشتهی دودویی را بیت به بیت می‌خواند و تشخیص می‌دهد عددش بر ۳ بخشپذیر است یا نه؛ بدون نگه داشتن خود عدد.زمان:
O(n) - تبدیل گرامر منظم به ماشین حالتاز یک گرامر منظم (قاعدههایی مثل A → aB) ماشین حالت معادل میسازد: هر ناپایانه یک حالت و هر قاعده یک یال؛ بعد رشتهای را روی آن امتحان می‌کند.زمان:
O(rules + |w| · edges) - تبدیل NFA به DFA (ساخت زیرمجموعه)ماشین ناقطعی را به ماشین قطعی معادل تبدیل می‌کند: هر حالت DFA مجموعهای از حالتهای NFA است که ماشین ناقطعی همزمان میتواند در آنها باشد.زمان:
O(2ⁿ) states in the worst case
درخت‌های رشته
- درخت جستوجوی رقمیمثل درخت جستوجوی دودویی است، ولی در عمق d بهجای مقایسهی کلیدها، بیت d ام کلید راه را تعیین می‌کند؛ ارتفاع هیچوقت از تعداد بیتها بیشتر نمیشود.زمان:
O(number of bits) per operation - طولانیترین پیشوند منطبق (مسیریابی IP)پیشوندهای جدول مسیریابی را در یک trie دودویی میگذارد و نشانی را بیت به بیت دنبال می‌کند؛ آخرین پیشوندی که در راه دیده شد بلندترین تطابق است.زمان:
O(address length) - درخت پسوندیهمهی پسوندهای رشته را در یک درخت فشرده میگذارد که هر یالش تکهای از متن است؛ بعد هر الگو را در O(طول الگو) می‌شود پیدا کرد.زمان:
O(n²) here (O(n) with Ukkonen's method) - درخت پیشوندی (Trie)کلمهها را حرف به حرف در درختی نگه میدارد که پیشوندهای مشترک یک مسیر مشترکاند؛ جست‌وجو فقط به طول کلمه بستگی دارد، نه به تعداد کلمهها.زمان:
O(word length) per insert or search
کدگذاری
- کد همینگ (۷،۴)به ۴ بیت داده ۳ بیت توازن اضافه می‌کند طوری که اگر یک بیت در راه خراب شود، «نشانگر» دقیقاً جای آن را بگوید و درستش کند.زمان:
O(1) - کدگذاری هافمنبرای هر نماد کدی دودویی میسازد که نمادهای پرتکرار کد کوتاهتری بگیرند: هر بار دو درخت سبکتر را زیر یک ریشه جمع می‌کند.زمان:
O(n + k log k) for k symbols
درخت
↑ همه‌ی موضوعهاپیمایش درخت
- کپی و برابری دو درختدو الگوریتم بازگشتی کوتاه: کپی یک درخت دودویی گره به گره، و بررسی اینکه دو درخت هم شکل و هم کلیدهایشان یکی است؛ هر دو O(n).زمان:
O(n) - پیمایش میانترتیب و پیشترتیب بدون بازگشتپیمایش درخت دودویی با یک پشتهی صریح به جای بازگشت: همان ترتیبها، ولی پشتهای که بازگشت پنهان میکرد دیده می‌شود.زمان:
Θ(n) - پیمایش سطحبهسطحگرههای درخت را سطحبهسطح، از بالا به پایین و از چپ به راست، با یک صف ملاقات می‌کند؛ همان BFS روی درخت.زمان:
O(n) - درخت دودویی نخکشیشدهپیوندهای راست خالی درخت را به جانشین میانترتیب هر گره وصل می‌کند (نخ)؛ بعد پیمایش میانترتیب بدون پشته و بدون بازگشت انجام می‌شود.زمان:
Θ(n) - یکریختی درختهابررسی می‌کند آیا دو درخت ریشهدار با جابهجا کردن فرزندان به هم تبدیل می‌شوند: به هر زیردرخت از پایین به بالا یک نام متعارف می‌دهد و نام دو ریشه را مقایسه می‌کند.زمان:
O(n²) with strings (O(n) with integer names) - پیمایشهای درختپیمایش پیشترتیب، میانترتیب و پسترتیب یک درخت دودویی با بازگشت؛ میانترتیبِ درخت جستجو کلیدها را مرتب می‌دهد.زمان:
O(n)
درخت جستجوی دودویی
- حذف از درخت AVLکلید را مثل درخت جستجوی معمولی حذف می‌کند و در مسیر برگشت به ریشه، هر گره‌ی نامتوازن را با چرخش درست می‌کند؛ برخلاف درج، ممکن است در چند سطح چرخش لازم شود. O(log n).زمان:
O(log n) - درخت AVL (درج)درخت جستوجوی دودویی که بعد از هر درج، با یک یا دو چرخش، اختلاف ارتفاع دو زیردرخت هر گره را حداکثر ۱ نگه میدارد.زمان:
O(log n) per insert - B-درختدرخت جستجوی متوازنی که هر گره چند کلید و چند فرزند دارد و همه‌ی برگها در یک عمقاند؛ گرههای پر در مسیر پایین رفتن شکافته می‌شوند. ساختهشده برای دیسک: ارتفاع O(log_t n).زمان:
O(t · log_t n) per insert - درج و حذف در درخت جستجوی دودوییکلید تازه با مقایسه از ریشه تا جای خالی پایین می‌رود؛ حذف سه حالت دارد: برگ، یک فرزند، و دو فرزند (با جانشین).زمان:
O(h) per operation (h = height) - پرسوجو در درخت جستوجوی دودوییکمینه، بیشینه، جست‌وجو و پسین در درخت جستوجوی دودویی؛ هر کدام فقط یک مسیر از ریشه به پایین را میپیماید.زمان:
O(h) - شکافتن و پیوند درخت جستجوی دودوییدرخت جستجو را با کلید k به دو درخت (کوچکتر و بزرگتر از k) میشکافد و بعد دو درخت را دوباره پیوند می‌دهد؛ هر دو O(h). شکافتن و سپس پیوند همان حذف k است.زمان:
O(h) - درخت بازه و جستوجوی همپوشانیدرخت جستجویی از بازهها که هر گره بزرگترین انتهای بازههای زیردرختش را نگه میدارد؛ با آن، بازهای که با بازهی پرسش همپوشانی دارد در O(h) پیدا می‌شود.زمان:
O(h) - درخت آمارهی ترتیبی (OS-Select و OS-Rank)درخت جستجویی که هر گره اندازهی زیردرختش را نگه میدارد؛ با آن، i-امین کوچک‌ترین کلید و رتبهی هر کلید در O(h) پیدا می‌شود.زمان:
O(h) - درخت قرمز–سیاه (درج)درخت جستوجوی دودویی متوازن با رنگ گرهها؛ بعد از هر درج، چرخش و عوض کردن رنگها تضمین می‌کند ارتفاع حداکثر 2 log n بماند.زمان:
O(log n) per insert - درخت اسپلیدرخت جستجویی بدون هیچ اطلاعات توازن: هر کلیدی که به آن دسترسی پیدا شود با چرخشهای دوتایی به ریشه میآید. هزینهی سرشکن هر عمل O(log n) است.زمان:
O(log n) amortized
ساختمان داده
↑ همه‌ی موضوعهالیستهای پیوندی
- فهرست فضای آزادگرههای آزاد یک مخزن را در یک لیست پیوندی نگه میدارد: گرفتن گره یعنی برداشتن از سر این لیست و پس دادن یعنی گذاشتن در سرش؛ هر دو O(1).زمان:
O(1) per operation - الحاق دو لیست پیوندیلیست دوم را به ته لیست اول وصل می‌کند: فقط تا آخرین گره‌ی لیست اول جلو می‌رود و یک اشارهگر را عوض می‌کند؛ هیچ گرهای کپی نمیشود.زمان:
O(length of the first list) - کلاسهای همارزیاز فهرستی از جفتهای i ≡ j، کلاسهای همارزی را پیدا می‌کند: هر جفت را در لیست هر دو عضو میگذارد و بعد با یک پشته همه‌ی اعضای یک کلاس را جمع می‌کند؛ O(n + m).زمان:
O(n + m) - لیست پیوندی مرتب (درج، جست‌وجو، حذف)عضوها را یکی‌یکی در جای درستشان در یک لیست پیوندی مرتب درج می‌کند و بعد عضوی را جست‌وجو و حذف می‌کند؛ فقط اشارهگرها عوض می‌شوند، هیچ عضوی جابهجا نمیشود.زمان:
O(n) per operation - برعکس کردن لیست پیوندیجهت همه‌ی پیوندهای لیست را با سه اشارهگر prev، cur و nxt یکی‌یکی برمیگرداند؛ در یک گذر و بدون حافظهی اضافه.زمان:
O(n)
پشته و صف
- صف حلقویصفی روی یک آرایهی با اندازهی ثابت که وقتی به انتهای آرایه رسید، از ابتدا ادامه می‌دهد؛ هر درج و حذف O(1) است و جای خالی هدر نمیرود.زمان:
O(1) per operation - دو پشته در یک آرایهدو پشته در یک آرایه از دو سر به سمت هم رشد می‌کنند؛ هیچکدام پر نمیشود مگر وقتی کل آرایه پر باشد.زمان:
O(1) per operation
تحلیل سرشکن
- شمارندهی دودویی (تحلیل سرشکن)یک شمارندهی دودویی را هشت بار یکی زیاد می‌کند؛ یک افزایش ممکن است بیتهای زیادی را عوض کند، ولی میانگین کمتر از ۲ است.زمان:
O(k) for one increment of k bits, O(1) amortized - جدول پویا (تحلیل سرشکن)آرایهای که هر وقت پر شد دو برابر می‌شود؛ کپیها گاهی گراناند ولی هزینهی سرشکن هر درج حداکثر ۳ است.زمان:
O(1) amortized per insert - پشته با MULTIPOP (تحلیل سرشکن)یک MULTIPOP ممکن است چند عضو را با هم بردارد و گران باشد، ولی هر عضو حداکثر یک بار برداشته می‌شود؛ پس هزینهی کل n عمل حداکثر 2n است.زمان:
O(1) amortized per operation
الگوریتم‌های برخط
- سیاستهای حافظهی نهان (LRU، FIFO، دورترین در آینده)سه حافظهی نهان با یک اندازه به یک دنبالهی درخواست جواب میدهند و تعداد خطاها مقایسه می‌شود؛ «دورترین در آینده» بهینه است ولی باید آینده را بداند.زمان:
O(n·k) (furthest-in-future: O(n²·k) here) - انتقال به جلو (Move-to-Front)لیستی که خودش را سازمان می‌دهد: هر عضوی که درخواست شد به جلوی لیست می‌رود، پس عضوهای پرکاربرد جلو میمانند؛ هزینهاش حداکثر ۴ برابر بهترین روش آفلاین است.زمان:
O(position) per request
هرم‌ها و صف‌های اولویت
- هرم دوجملهایجنگلی از درخت‌های دوجملهای با درجههای متفاوت، مثل ارقام دودویی n؛ ادغام دو هرم مثل جمع دو عدد دودویی است و در O(log n) انجام می‌شود.زمان:
O(log n) per union, insert or extract-min - هرم فیبوناچیهرمی که کار را تا جای ممکن عقب میاندازد: درج و کاهش کلید O(1) سرشکناند و فقط حذف کمینه درختها را مرتب می‌کند (O(log n) سرشکن). برش آبشاری درختها را پرپشت نگه میدارد.زمان:
O(1) amortized insert and decrease-key; O(log n) amortized extract-min - هرم چپگرا (Leftist)هرمی که دو هرم را در O(log n) ادغام می‌کند: همه‌ی کار روی ستون راست کوتاه انجام می‌شود و هر جا سمت چپ کوتاهتر شد، دو فرزند جابهجا می‌شوند. درج و حذف کمینه هم همان ادغاماند.زمان:
O(log n) per merge, insert or delete-min - هرم کمینه-بیشینههرمی که سطرهای زوجش هرم کمینه و سطرهای فردش هرم بیشینهاند؛ هم کمینه و هم بیشینه در O(1) پیدا و در O(log n) حذف می‌شوند (صف اولویت دوطرفه).زمان:
O(log n) per insert or delete; O(1) to find the min or max - درخت برنده (و بازنده) برای ادغام k-راههk فهرست مرتب را با یک درخت مسابقه ادغام می‌کند: ریشه کوچک‌ترین سر فهرستهاست و بعد از هر خروجی، فقط بازیهای یک مسیر برگ تا ریشه دوباره انجام می‌شود؛ O(log k) برای هر عضو.زمان:
O(n log k) for n items in k runs
برنامه‌ریزی پویا
↑ همه‌ی موضوعهامسئلههای کلاسیک
- مجموع زیرمجموعه (طرح تقریب کاملاً چندجمله‌ای)بزرگترین جمع زیرمجموعهای را که از t بیشتر نشود تقریب می‌زند؛ با هرس جمعهای نزدیک به هم، فهرست کوتاه میماند و جواب حداکثر (1 + ε) برابر کمتر از بهینه است.زمان:
O(n² ln t / ε) - بلندترین زیردنبالهی مشترک (LCS)بلندترین زیردنبالهای که در هر دو رشته (به همان ترتیب، نه لزوماً پشت سر هم) آمده است را با جدول برنامه‌ریزی پویا پیدا می‌کند.زمان:
O(m·n) - ضرب زنجیرهای ماتریسهابهترین پرانتزگذاری برای ضرب چند ماتریس را با برنامه‌ریزی پویا پیدا می‌کند؛ ترتیب ضربها تعداد ضربهای عددی را تا چند برابر عوض می‌کند.زمان:
O(n³) - درخت جستجوی دودویی بهینهبا برنامه‌ریزی پویا درخت جستجویی میسازد که با دانستن بسامد جستوجوی هر کلید، کمترین هزینهی مورد انتظار را دارد؛ برای هر بازهی کلیدها، بهترین ریشه را امتحان می‌کند. O(n³).زمان:
Θ(n³) (O(n²) with Knuth's speed-up) - برش میلهمیلهای به طول n را طوری ببُر که فروش تکهها بیشترین درآمد را بدهد؛ جواب هر طول از جواب طولهای کوتاهتر ساخته می‌شود.زمان:
O(n²)
الگوریتم‌های حریصانه
↑ همه‌ی موضوعهامسئلههای کلاسیک
- انتخاب فعالیتهابیشترین تعداد فعالیت بدون همپوشانی را انتخاب می‌کند: همیشه فعالیتی که زودتر تمام می‌شود، اگر با قبلی تداخل نداشته باشد.زمان:
O(n log n) - کولهپشتی کسریکولهپشتی با ظرفیت W را با بیشترین ارزش پر می‌کند وقتی می‌شود کسری از هر کالا برداشت: کالاها به ترتیب ارزش هر واحد وزن.زمان:
O(n log n) - پوشش مجموعهای حریصانههر بار مجموعهای را برمی‌دارد که بیشترین عضو پوششدادهنشده را دارد؛ حداکثر H(max |S|) ≈ ln n برابر کمترین تعداد مجموعه‌ی لازم.زمان:
O(|X| · |F| · min(|X|, |F|)) - ادغام بهینهی دنبالههاچند دنبالهی مرتب با اندازههای مختلف را دوبهدو ادغام می‌کند؛ اگر هر بار دو تای کوچکتر ادغام شوند، هزینهی کل کمینه است.زمان:
O(n log n)
عددها
↑ همه‌ی موضوعهانظریهی اعداد
- تبدیل مبناعدد را با تقسیمهای پیاپی بر مبنا به مبنای دیگر میبرد؛ باقیماندهها از آخر به اول، رقمهای جواباند.زمان:
O(log_b n) - قضیهی باقیماندهی چینیعددی را پیدا می‌کند که به چند پیمانهی نسبت به هم اول، باقیماندههای دادهشده را داشته باشد؛ هر جمله فقط در یک پیمانه اثر دارد.زمان:
O(k log N) - الگوریتم تقسیمخارجقسمت q و باقیماندهی r را طوری پیدا می‌کند که a = q·b + r و 0 ≤ r < b؛ با کم کردن یا اضافه کردن پیاپی b.زمان:
O(|a| / b) - الگوریتم اقلیدس (ب.م.م)بزرگترین مقسومعلیه مشترک دو عدد را با تقسیمهای پیاپی پیدا می‌کند: ب.م.م(a, b) = ب.م.م(b, a mod b).زمان:
O(log min(a, b)) - الگوریتم اقلیدس توسعهیافتهعلاوه بر ب.م.م، ضرایب s و t را پیدا می‌کند که s·a + t·b = ب.م.م(a, b)؛ پایهی وارون پیمانهای و RSA.زمان:
O(log min(a, b)) - حل معادلهی همنهشتی خطی (وارون پیمانهای)همه‌ی x هایی را پیدا می‌کند که a·x ≡ b (mod n)؛ با اقلیدس توسعهیافته. وارون پیمانهای حالت b = 1 است.زمان:
O(log n + d) - مولد همنهشتی خطی (عدد شبهتصادفی)عددهای «تصادفینما» با فرمول x ← (a·x + c) mod m میسازد؛ دنباله بالاخره تکرار می‌شود و انتخاب a، c و m طول دوره را تعیین می‌کند.زمان:
O(count) - آزمون اول بودن میلر–رابینبا توان پیمانهای و ریشههای ۱ تشخیص می‌دهد عدد مرکب است یا اول؛ حتی عددهای کارمایکل را که آزمون فرما گول میخورد.زمان:
O(k log³ n) - توان پیمانهای (مربعسازی پیاپی)aᵇ mod n را با حدود log b ضرب حساب می‌کند: پایه را پشت سر هم مربع می‌کند و برای هر بیت ۱ توان، آن را در جواب ضرب می‌کند.زمان:
O(log b) - الگوریتم رو پولاردیک عامل عدد مرکب n را با دنبالهی x² + 1 پیدا می‌کند: دو اشارهگر کند و تند روی دنباله میروند تا ب.م.م اختلافشان با n عاملی بدهد.زمان:
about O(n^¼) steps - آزمون اول بودن (تقسیم آزمایشی)n را بر ۲، ۳، … تا √n تقسیم می‌کند؛ اگر هیچکدام n را نشمارد، n اول است.زمان:
O(√n) - رمزنگاری RSAکلید عمومی (e, n) و خصوصی (d, n) را از دو عدد اول میسازد، پیام را با توان پیمانهای رمز می‌کند و دوباره برمیگرداند.زمان:
O(log e + log d) multiplications
شمارش و ترکیبیات
- شمارش با لم برنساید و روش پولیا (گردنبندها)تعداد گردنبندهای n مهرهای با k رنگ را میشمارد، وقتی چرخاندن (و برگرداندن) گردنبند آن را عوض نکند: میانگین تعداد رنگآمیزیهایی که هر تقارن ثابت نگه میدارد، و هر تقارن با c دور، k^c رنگ‌آمیزی را ثابت نگه میدارد.زمان:
O(n log n) - عددهای کاتالانعددهای کاتالان را با برنامه‌ریزی پویا حساب می‌کند؛ تعداد درخت‌های دودویی، پرانتزگذاریهای درست و مسیرهای زیر قطر همین عددهاست.زمان:
O(n²) - شمارش درخت‌های دودویی (بازگشتی)تعداد درخت‌های دودویی با n گره را مستقیم از تعریف بازگشتی میشمارد؛ درخت فراخوانی نشان می‌دهد چرا نسخهی پویا (عددهای کاتالان) بهتر است.زمان:
O(3ⁿ) - پریشها (جایگشتهای بینقطهی ثابت)تعداد جایگشتهایی را که هیچ عضوی سر جای خودش نیست میشمارد؛ نسبت آن به همه‌ی جایگشتها به 1/e نزدیک می‌شود.زمان:
O(n) - کد گریهمهی رشتههای n بیتی را طوری مرتب می‌کند که هر دو رشتهی پشت سر هم فقط در یک بیت فرق داشته باشند؛ با بازتاب فهرست قبلی.زمان:
O(n · 2ⁿ) - افراز عدد صحیحمیشمارد n به چند طریق جمع عددهای مثبت می‌شود (ترتیب مهم نیست)؛ با برنامه‌ریزی پویا، قسمتها یکی‌یکی مجاز می‌شوند.زمان:
O(n²) - مربع جادوییعددهای ۱ تا n² را در جدول n×n (n فرد) طوری می‌چیند که جمع هر سطر، ستون و قطر برابر شود؛ با روش سیامی: یکی بالا و یکی راست.زمان:
O(n²) - مربعهای لاتین متعامدبرای n اول، دو مربع لاتین n × n با فرمول (a·i + j) mod n میسازد که متعامدند: وقتی روی هم گذاشته شوند، هر جفت مرتب از نمادها دقیقاً یک بار میآید. در طراحی آزمایشها به کار می‌رود.زمان:
O(n²) to build (O(n⁴) for this simple check) - چندجمله‌ای رختعداد راههای گذاشتن k رخ بیتهدید روی یک صفحهی دلخواه را برای همه‌ی k میشمارد، با قاعده‌ی r(C) = x·r(C_s) + r(C_e) روی یک خانهی انتخابی s. در شمارش جایگشتهایی با جاهای ممنوع (اصل شمول و عدم شمول) به کار می‌رود.زمان:
O(2^c) for c cells
بازگشت و عقبگرد
- فاکتوریل بازگشتیn! = n · (n−1)! سادهترین مثال بازگشت: فراخوانیها تا حالت پایه روی پشته جمع می‌شوند و بعد در برگشت ضربها انجام می‌شود.زمان:
O(n) - فیبوناچی بازگشتیF(n) = F(n−1) + F(n−2) را مستقیم با بازگشت حساب می‌کند؛ درخت فراخوانیها نشان می‌دهد چرا این روش نمایی است.زمان:
O(φⁿ) ≈ O(1.618ⁿ) - تولید همه‌ی ترکیبهاهمهی زیرمجموعههای k عضوی از ۱ تا n را به ترتیب لغتنامهای میسازد؛ هر عضو بعدی از قبلی بزرگتر است تا هیچ زیرمجموعهای دو بار نیاید.زمان:
O(k · C(n, k)) - تولید همه‌ی جایگشتهاهمهی n! جایگشت ۱ تا n را به ترتیب لغتنامهای میسازد: هر بار یک عضو استفادهنشده را اضافه می‌کند و بعد عقب برمی‌گردد.زمان:
O(n · n!) - معمای دیوانگی آنی (Instant Insanity)چهار مکعب رنگی را طوری روی هم بچین که هر طرف ستون هر چهار رنگ را داشته باشد: جفت وجههای روبهروی هر مکعب یالهای یک گراف روی رنگها می‌شوند، و دنبال دو زیرگراف جدا میگردیم که در هر کدام هر رنگ دو بار بیاید.زمان:
O(3^n · 2^n) in the worst case - مسیریابی در هزارتو (عقبگرد)از گوشه‌ی بالا-چپ تا گوشه‌ی پایین-راست راه پیدا می‌کند: جلو می‌رود و هر جا بن‌بست بود علامت می‌زند و عقب برمی‌گردد.زمان:
O(rows · cols) - مسئلهی n وزیرn وزیر را طوری روی صفحهی n×n میگذارد که هیچ دو تایی هم را تهدید نکنند؛ سطر به سطر، و در بن‌بست عقب برمی‌گردد.زمان:
O(n!) worst case - برجهای هانویn دیسک را از میلهی A به C میبرد، هر بار یک دیسک و هیچوقت دیسک بزرگ روی کوچک؛ دقیقاً 2ⁿ − 1 حرکت.زمان:
O(2ⁿ) - کاشیکاری با ترومینوصفحهی 2^k × 2^k با یک خانهی کم را با کاشیهای L شکل سهخانهای میپوشاند: صفحه را چهار تکه می‌کند، یک ترومینو در وسط میگذارد تا هر تکه دقیقاً یک خانهی پر داشته باشد، و هر تکه را بازگشتی حل می‌کند. اثبات استقرایی به شکل الگوریتم.زمان:
Θ(4^k) (one step per tromino)
ماتریس و چندجمله‌ای
↑ همه‌ی موضوعهاعملهای ماتریسی
- ترانهادهی سریع ماتریس خلوتماتریس خلوت را بهصورت سهتاییهای (سطر، ستون، مقدار) نگه میدارد و ترانهادهاش را بدون مرتب‌سازی، با شمردن جملههای هر ستون، در O(ستونها + جملهها) میسازد.زمان:
O(cols + terms) - ضرب ماتریسهاماتریس n×m را در m×p ضرب می‌کند: هر خانهی حاصل، ضرب داخلی یک سطر از A و یک ستون از B است.زمان:
O(n·m·p) - ضرب ماتریسهای خلوتهر سطر را فقط با جملههای ناصفرش نگه میدارد و فقط ضربهای ناصفر را انجام می‌دهد؛ برای ماتریسهای خلوت خیلی کمتر از n³ ضرب.زمان:
O(rows + the number of non-zero products) - ضرب ماتریس اشتراسنضرب ماتریسهای n×n با تقسیم و حل: بهجای ۸ ضرب نیماندازه، ۷ تا با چند جمع و تفریق اضافه؛ زمان O(n^2.81).زمان:
O(n^log₂7) ≈ O(n^2.81)
جبر خطی عددی
- کمترین مربعات (برازش خط)خطی را پیدا می‌کند که جمع مربع فاصلههای عمودی نقطهها از آن کمترین باشد؛ با حل دو معادلهی نرمال، با کسرهای دقیق.زمان:
O(n) - حل دستگاه معادلات خطیA·x = b را با تجزیهی LUP و دو جایگذاری حل می‌کند: اول L·y = P·b رو به جلو، بعد U·x = y رو به عقب؛ با کسرهای دقیق.زمان:
O(n³), then O(n²) for each new b - تجزیهی LUPماتریس مربعی را به P·A = L·U میشکند (L پایینمثلثی، U بالامثلثی، P جایگشت سطرها) با حذف گاوسی و انتخاب محور جزئی؛ با کسرهای دقیق.زمان:
O(n³) - وارون ماتریس (گاوس–جردن)ماتریس [A | I] را با عمل‌های سطری به [I | A⁻¹] میرساند؛ هر ستون یک محور ۱ میگیرد و بالا و پایینش صفر می‌شود. با کسرهای دقیق.زمان:
O(n³)
چندجمله‌ای‌ها
- تبدیل فوریهی سریع (FFT)مقدار چندجمله‌ای را در n ریشهی واحد با تقسیم و حل در O(n log n) حساب می‌کند (و برعکس، با FFT وارون)؛ پایهی ضرب سریع چندجمله‌ای‌ها.زمان:
O(n log n) - ضرب چندجمله‌ای‌ها با FFTدو چندجمله‌ای را در O(n log n) ضرب می‌کند: هر دو را در ریشههای واحد ارزیابی می‌کند، مقدارها را نقطه به نقطه ضرب می‌کند و با FFT وارون ضریبها را برمیگرداند.زمان:
O(n log n) - روش هورنر (مقدار چندجمله‌ای)مقدار چندجمله‌ای درجهی n را فقط با n ضرب و n جمع حساب می‌کند: x را پشت سر هم بیرون میکشد.زمان:
O(n) - جمع چندجملهایهادو چندجمله‌ای خلوت را که فقط جملههای ناصفرشان نگه داشته شده جمع می‌کند؛ مثل ادغام در مرتب‌سازی ادغامی، به ترتیب توان.زمان:
O(m + n)
منطق و مدار
↑ همه‌ی موضوعهامنطق گزاره‌ای
- جدول کارنو و صورتهای DNF و CNFاز سطرهای درست جدول درستی، صورت متعارف فصلی (DNF) و عطفی (CNF) را میسازد و بعد مثل جدول کارنو، خانههای همسایه را ادغام می‌کند (روش کوین–مککلاسکی) تا سادهترین مجموع حاصلضربها به دست آید.زمان:
O(3^n · n) for the prime implicants - MAX-3-CNF: تقریب ۷/۸ تصادفی و قطعیشدهیک مقداردهی تصادفی به طور میانگین ۷/۸ بندهای 3-CNF را درست می‌کند. با «امید شرطی» متغیرها را یکی‌یکی طوری تعیین میکنیم که امید کم نشود؛ نتیجه قطعاً حداقل ۷/۸ بندها را درست می‌کند.زمان:
O(n · m) - رزولوشن (اثبات با تفکیک)از دو بند که یکی ℓ و دیگری ¬ℓ را دارد، بند تازهای میسازد که بقیهی هر دو را دارد. اگر به بند تهی برسیم، مجموعه‌ی بندها ناسازگار است؛ اثبات با برهان خلف به همین شکل است.زمان:
exponential in the worst case - درخت عبارت و مسئلهی صدقپذیرییک فرمول گزاره‌ای را به درخت عبارت تبدیل می‌کند و آن را برای هر مقداردهی متغیرها با پیمایش پسترتیب ارزیابی می‌کند؛ فرمول صدقپذیر است اگر سطری درست شود. 2^n مقداردهی.زمان:
O(2^n · size) - جدول درستیبرای هر مقداردهی متغیرها، ارزش هر زیرفرمول را از داخل به بیرون حساب می‌کند و در پایان میگوید فرمول همیشه درست (راستگو)، همیشه نادرست (تناقض) یا گاهی درست است.زمان:
O(2^n · size)
یادگیری ماشین
↑ همه‌ی موضوعهاالگوریتمهای یادگیری ماشین
- گرادیان کاهشیبرای کمینه کردن یک تابع، قدم به قدم در خلاف جهت گرادیان حرکت می‌کند. اینجا خطی را به چند نقطه برازش می‌دهد (کمترین مربعات). اندازهی گام (نرخ یادگیری) تعیین می‌کند همگرا شود یا واگرا.زمان:
O(n) per step - خوشهبندی k-میانگیننقطهها را به k خوشه تقسیم می‌کند: هر نقطه به نزدیکترین مرکز میپیوندد و هر مرکز به میانگین نقطههایش می‌رود، تا وقتی هیچ نقطهای خوشهاش را عوض نکند. هزینه هر دور کم می‌شود، ولی جواب ممکن است بهینهی موضعی باشد.زمان:
O(n · k) per round - وزنهای ضربی (اکثریت وزندار)از چند «کارشناس» پیشبینی میگیرد و طبق رأی وزندار آنها پیشبینی می‌کند؛ هر کارشناسی که اشتباه کرد وزنش ضربدر (1 − ε) می‌شود. تعداد اشتباهها حداکثر حدود ۲ برابر بهترین کارشناس به اضافهی O(log n/ε) است.زمان:
O(n) per round