۰
subtitle
جواب سوال چهار "خیر" است.
چون که شما می دانید برای مرتب سازی یک لیست ساده و معمولی ا اعداد حقیقی با n عنصر حداقل به nlogn زمان نیاز دارید
یک نکته ای که در حل این سوال به شما کمک می کند این است که بداینید هر لیست ساده و معمولی از اعداد حقیقی رو می شه به راحتی و در زمان O(n) به یک لیست زیگزاگی (bitonic) تبدیل کرد.
چطوری؟
این طورری که شما کوچکترین عنصر لیست را در O(n) پیدا می نید بعد میایید از اول لیست یکی در میان بین اعداد یه عدد خیلی کوچکتر از مینیمم قرار می دهید. با این کار تعداد اعضای لیستتون دو برابر می شه ولی لیستتون به صورت زیگزاگی در میاد
پس هر لیست معمولی ای که به ما بدن در O(n) می توان آن را به لیست زیگزاگی تبدیل کرد
حال اگر ادعای این سوال درست باشد و بتوانیم لیست زیگزگی را در O(n) مرتب کنیم
پس هر لیست معمولی را می توان در O(n) مرتب کرد که این غلط است زیرا برای مرتب سازی حداقل به nlogn زمان احتیا داریم
چون که شما می دانید برای مرتب سازی یک لیست ساده و معمولی ا اعداد حقیقی با n عنصر حداقل به nlogn زمان نیاز دارید
یک نکته ای که در حل این سوال به شما کمک می کند این است که بداینید هر لیست ساده و معمولی از اعداد حقیقی رو می شه به راحتی و در زمان O(n) به یک لیست زیگزاگی (bitonic) تبدیل کرد.
چطوری؟
این طورری که شما کوچکترین عنصر لیست را در O(n) پیدا می نید بعد میایید از اول لیست یکی در میان بین اعداد یه عدد خیلی کوچکتر از مینیمم قرار می دهید. با این کار تعداد اعضای لیستتون دو برابر می شه ولی لیستتون به صورت زیگزاگی در میاد
پس هر لیست معمولی ای که به ما بدن در O(n) می توان آن را به لیست زیگزاگی تبدیل کرد
حال اگر ادعای این سوال درست باشد و بتوانیم لیست زیگزگی را در O(n) مرتب کنیم
پس هر لیست معمولی را می توان در O(n) مرتب کرد که این غلط است زیرا برای مرتب سازی حداقل به nlogn زمان احتیا داریم
