چندریسه‌ای+مرتب سازی روی پروانه

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

مثال فیبوناچی هم طبیعتاً ربطی به این قضایا نداره چون اون خودش رابطه بازگشتی‌اش حل کردنش به صورت موازی O(n) زمان می‌خواهد. (طول مسیر بحرانی)

-------

برای مرتب سازی روی مدل پروانه‌ای هم bitonic sort را نوشتم در حالی که به خاطر اینکه روی پروانه داریم اجرا می‌کنیم ترتیبش یک جور دیگه باید باشه که من سر جلسه هر کاری کردم بهتر از اون نشد. توی کتاب هم گفته به صورت بازگشتی این کار را انجام می‌دهیم و اصلاً معلوم نیست چطوری این کار را کرده. :|

--------

فکر کنم هدف سوال ۲ هم این بود که حلقه موازی بنویسیم نه اینکه مثل من کل مسأله را در زمان log n حل کنیم! :) :|