ارزیابی بازار بورس
 | این مقاله دارای چندین مشکل است. خواهشمندیم به بهبود آن کمک کنید یا در مورد این مشکلات در صفحهٔ بحث گفتگو کنید. (دربارهٔ چگونگی و زمان مناسب برداشتن این برچسبها بیشتر بدانید)
|
 | این مقاله نیازمند ویکیسازی است. لطفاً با توجه به راهنمای ویرایش و شیوهنامه، محتوای آن را بهبود بخشید. (مه ۲۰۱۰) |
در بازار بورس، آخرین قیمت سهام هر شرکت در انتهای هر روز تهیه می‌شود و بر روی این داده‌ها تحلیل‌های مختلف انجام می‌گیرد. فرض کنید می‌خواهیم در هر روز «دورهٔ سهام» یک شرکت خاص را پیدا کنیم به این صورت که اگر قیمت سهام آن شرکت در روز iبرابر pi باشد دورهٔ سهام در روز i برابر است با تعداد روزهای بلافاصله قبل از i(و شامل خود i) که قیمت سهام کمتر یا مساوی pi باشد. اگر قیمت سهام یک شرکت درn روز متوالی در یک آرایه ی n تایی به نام P ذخیره شده باشد، می‌خواهیم در خروجی آرایهٔ n تایی S را محاسبه کنیم که Si دورهٔ سهام آن شرکت در روز i باشد.
الگوریتم کند[ویرایش]
با یک الگوریتم کند از مرتبه ی(۲^O(n می‌توان این مسئله را به صورت زیر حل کرد:
بدترین حالت الگوریتم کند[ویرایش]
بدترین حالت الگوریتم کند زمانی است که عناصر به صورت صعودی SORT شده باشند و در واقع برای پیدا کردن بازهٔ هر عنصر باید همهٔ عناصر ماقبلش پیمایش بشه که این موضوع توضیحی برای غیر بهینه بودن آن می‌باشد.
الگوریتم خطی[ویرایش]
نکتهٔ مهم در حل سریع این مسئله این است که برای بدست آوردن دورهٔ سهام در روز i نیاز به بررسی قیمت سهام در همهٔ روزهای قبل از آن نیست بلکه کافی است از بین این قیمتها آن‌هایی را نگه داریم که به ازای t1<t۲<…<tk=i-۱ داشته باشیم pt1>pt2>…>ptk، به‌طوری‌که همهٔ مقادیر سهام بین روزهای ti و ti+۱ بین دو مقدار pti وpti+۱ باشد .(به شکل زیرمراجعه کنید). اگر این اطلاعات را داشته باشیم می‌توان به سادگی Si را بدست آوردPi را با ptk مقایسه می‌کنیم اگر از آن کمتر بود که بازهٔ … ام به دست می‌آید و گرنه باید با … مقایسه کنیم چرا که بقیهٔ قیمتها در این بازه ازPtk کم ترند و نیازی به بررسی آن‌ها نیست. این کاررا تکرار می‌کنیم تا به بزرگ‌ترین r ای برسیم که>Ptr+1 Ptr >Piدر آن صورت i-tr دورهٔ i ام است. البته اگرpt۱ ← pi در آن صورت iجواب است. در هر مرحله اعداد را در پشته ی Dذخیره می‌کنیم به‌طوری‌که Ptk در بالای پشته قرار گیرد. رویه یCompute Spans۲ این کار را انجام می‌دهد.
شکل بالا، قیمت روزانهٔ سهام یک شرکت در بازار بورس (pi) و دورهٔ سهام آن در هر روز (si) را نمایش می‌دهد.
مراحل الگوریتم خطی مسئلهٔ بازار بورس[ویرایش]
یک پشته به نام D می‌سازیم و شمارهٔ روزهای ماه را داخلش درج می‌کنیم
محاسبهٔ دوره‌های سهام = compute spans
هر روزی ارزشی دارد که اینجا با pi نشان داده شده ما به دنبال آن هستیم که ببینیم این pi تا چند روز قبل از خودش بیشترین مقداربوده، پس کافیست که بدانیم در روزهای قبل، اولین جایی که یک pj ای وجود داشته که از آن بزرگ‌تر بوده کجا بوده؟ به همین منظور یک استک ایجاد می‌کنیم، در ابتدا پشته خالیست پس p۰ رو در آن درج می‌کنیم و مسلماً s۰، می‌شود ۱، حالا برای بقیهٔ درج‌ها نیز این کار را انجام می‌دهیم، مثلاً فرض کنید می‌خواهیم pi را درج کنیم، اگر پشته خالی بودیعنی هیچ روزی قبل از روز iام نبوده که ازpi بزرگ‌تر باشد، بنابراین جواب، i می‌شود. در غیر این صورت pi را با عتصر بالای پشته مقایسه می‌کنیم اگر عتصر بالای پشته بزرگ‌تر از pi بودpi را روی پشته می‌گذاریم و si برابر می‌شود با اختلاف روز iام با روزی که روی پشته هست اما اگر عتصر بالای پشته کوچک‌تر بود، این قدر از پشته pop می‌کنیم تا یا پشته خالی شود، یا به عددی برسیم که از pi بزرگ تراست در آن صورت، جواب همان اختلاف روز iام با عتصر بالای پشته می‌شود.
زمان اجرای الگوریتم[ویرایش]
زمان اجرای این الگوریتم از (O(n است چرا که هر pi دقیقاً یک بار وارد پشته و حداکثر یک بار از آن خارج می‌شود
منابع[ویرایش]
کتاب :داده ساختارها و مبانی الگوریتم‌ها
مؤلف:محمد قدسی
انتشارات :فاطمی
صفحات: ۱۵۰٬۱۵۱٬۱۵۲
 | این مقاله در هیچ ردهٔ محتوایی قرار نگرفته است. لطفاً با افزودن چند رده کمک کنید تا این مقاله در کنار سایر مقالههای مشابه فهرست شود. (اوت ۲۰۲۲) |