جدول پراکنده ( به انگلیسی:sparse table ) مفهومی است که برای جستجوی سریع در مجموعه ای از داده های استاتیک ( داده هایی که تغییر نمی کنند ) استفاده می شود و پیش پردازشی بر روی داده ها انجام می دهد تا به سوالات کاربر در ارتباط با داده ها پاسخ دهد.
یک آرایه را در نظر بگیرید شامل n عضو از یک مجموعه منظم ( خوش ترتیب ) مانند مجموعه اعداد باشد، می توان به کمک یک جدول پراکنده درهرمرحله طبق خواسته کاربر خروجی مورد نیاز او را بدون نیاز به صرف زمان زیاد چاپ کرد. خواسته کاربر می تواند موارد مختلفی را شامل شود که به تفکیک هرکدام را بررسی خواهیم کرد.
در این موارد می توان از جدول پراکنده کمک گرفت:
• جستجوی ماکسیمم بازه ای
• جستجوی بزرگترین مقسوم علیه مشترک بازه ای
• جستجوی مینیمم بازه ای
• جستجوی مجموع بازه ای
یکی از موارد استفاده جدول پراکنده در جستجوی ماکسیمم هر بازه مورد نیاز کاربر است. بدین صورت که:
آرایه ای مانند A را درنظر بگیرید، درهر مرحله یک بازه داده می شود که باید بزرگترین عدد در آن بازه را پیدا کرد. بازه های ما به شکل Q = هستند که L ابتدای بازه ی و R انتهای بازه را نشان می دهند و نیز این عبارت برای هر L و R برقرار است: 0 ≤ L ≤ R ≤ n − 1 ، به عنوان مثال آرایه A = { 6 , 7 , 4 , 5 , 1 , 3 } را در نظر بگیرید که در بازه ی Q 1 = بزرگترین عدد 7 ، در بازه ی Q 2 = بزرگترین عدد 5 و در بازه Q 3 = نیز بزرگترین عدد 5 می باشد.
حال اگر تعداد بازه ها افزایش یابند این عمل نیازمند زمان زیادی است که بخواهیم تک تک اعداد آن بازه را بررسی کنیم ، به جای آن می توان از جدول پراکنده کمک گرفت و پاسخ هر بازه را بسیار سریع و در زمان O ( 1 ) پیدا کرد.
می توان قبل از شروع پرسش داده هایمان را پیش پردازش کنیم و ماکسیمم تمامی زیرآرایه ها به طول 2 j که j در بازه 0 تا log n قرار دارد را بیابیم.
برای این کار یک جدول پراکنده به نام l o o k u p ایجاد می کنیم که ماکسیمم تمامی بازه ها با شروع از i و به طول 2 j را در بردارد. برای پر کردن این جدول از طراحی پایین به بالا استفاده می کنیم و در مراحل بالاتر از نتایج مراحل پایین تر کمک می گیریم، به این صورت که برای یافتن ماکسیمم در بازه ی از ماکسیمم های دو بازه و استفاده میکنیم که بزرگترین آن ها ماکسیمم کل می باشد.
این نوشته برگرفته از سایت ویکی پدیا می باشد، اگر نادرست یا توهین آمیز است، لطفا گزارش دهید: گزارش تخلفیک آرایه را در نظر بگیرید شامل n عضو از یک مجموعه منظم ( خوش ترتیب ) مانند مجموعه اعداد باشد، می توان به کمک یک جدول پراکنده درهرمرحله طبق خواسته کاربر خروجی مورد نیاز او را بدون نیاز به صرف زمان زیاد چاپ کرد. خواسته کاربر می تواند موارد مختلفی را شامل شود که به تفکیک هرکدام را بررسی خواهیم کرد.
در این موارد می توان از جدول پراکنده کمک گرفت:
• جستجوی ماکسیمم بازه ای
• جستجوی بزرگترین مقسوم علیه مشترک بازه ای
• جستجوی مینیمم بازه ای
• جستجوی مجموع بازه ای
یکی از موارد استفاده جدول پراکنده در جستجوی ماکسیمم هر بازه مورد نیاز کاربر است. بدین صورت که:
آرایه ای مانند A را درنظر بگیرید، درهر مرحله یک بازه داده می شود که باید بزرگترین عدد در آن بازه را پیدا کرد. بازه های ما به شکل Q = هستند که L ابتدای بازه ی و R انتهای بازه را نشان می دهند و نیز این عبارت برای هر L و R برقرار است: 0 ≤ L ≤ R ≤ n − 1 ، به عنوان مثال آرایه A = { 6 , 7 , 4 , 5 , 1 , 3 } را در نظر بگیرید که در بازه ی Q 1 = بزرگترین عدد 7 ، در بازه ی Q 2 = بزرگترین عدد 5 و در بازه Q 3 = نیز بزرگترین عدد 5 می باشد.
حال اگر تعداد بازه ها افزایش یابند این عمل نیازمند زمان زیادی است که بخواهیم تک تک اعداد آن بازه را بررسی کنیم ، به جای آن می توان از جدول پراکنده کمک گرفت و پاسخ هر بازه را بسیار سریع و در زمان O ( 1 ) پیدا کرد.
می توان قبل از شروع پرسش داده هایمان را پیش پردازش کنیم و ماکسیمم تمامی زیرآرایه ها به طول 2 j که j در بازه 0 تا log n قرار دارد را بیابیم.
برای این کار یک جدول پراکنده به نام l o o k u p ایجاد می کنیم که ماکسیمم تمامی بازه ها با شروع از i و به طول 2 j را در بردارد. برای پر کردن این جدول از طراحی پایین به بالا استفاده می کنیم و در مراحل بالاتر از نتایج مراحل پایین تر کمک می گیریم، به این صورت که برای یافتن ماکسیمم در بازه ی از ماکسیمم های دو بازه و استفاده میکنیم که بزرگترین آن ها ماکسیمم کل می باشد.
wiki: جدول پراکنده