در علوم کامپیوتر، جمع پیشوندی به آرایه ای گفته می شود که هر عنصر آن ( y 0 , y 1 , y 2 , . . . ) از جمع چند عدد ورودی متوالی به صورت زیر حاصل می شود. [ ۱]
y 0 = x 0
y 1 = x 0 + x 1
y 2 = x 0 + x 1 + x 2
. . .
برای نمونه، به جدول زیر توجه کنید.
همچنین می توان با درنظرگرفتن y 0 = x 0 , y i را با استفاده از فرمول y i = y i − 1 + x i بدست آورد. علی رغم سادگی در پیاده سازی، جمع پیشوندی در الگوریتم های خاص همچون مرتب سازی شمارشی، در زبان های برنامه نویسی تابعی در تشکیل پایه ای برای اسکن توابع مرتبه بالا و در الگوریتم های موازی مورد مطالعه قرار گرفته است. زمان صرف شده برای محاسبهٔ جمع پیشوندی از مرتبهٔ ( O ( n می باشد، حافظه ای که برای ساختن آن صرف می شود نیز ( O ( n می باشد اما در جمع پیشوندی موازی می توان حافظهٔ استعمال شده را به ( O ( logn کاهش داد.
نحوه پیاده سازی جمع پیشوندی در زبان های جاوا، پایتون و سی {به انگلیسی:به ترتیب:C, python, java} نشان داده شده است.
int* prefixSums ( int input, int output, int length ) { output = input; int i; for ( i = 1; i < length; i++ ) output = output + input; return output; پیاده سازی با کد جاوا static int prefixSums ( int input, int output ) { output = input; for ( int i = 0; i < input. length; i++ ) output = output + input; return output; } پیاده سازی پایتون def prefixSums ( input, output ) : output = input; for i in range ( 1, len ( input ) ) : output = output + input کاربردها مرتب سازی شمارشی گونه ای از مرتب سازی های خطی است که بدون مقایسه، عمل مرتب سازی عناصر یک آرایه را انجام می دهد. در مرتب سازی شمارشی، از جمع پیشوندی برای یافتن جایگاه هر عنصر در آرایه مرتب شده، استفاده می شود. [ ۲]
در رتبه بندی لیست ها، برای تبدیل یک لیست پیوندی به یک آرایه خروجی، از جمع پیشوندی استفاده می شود بدین نحو که یک آرایهٔ ورودی از ۱ها به اندازه طول لیست پیوندی ساخته می شود سپس با استفاده از جمع پیشوندی این آرایه، اندیس متناظر برای نگاشتن هر عنصر در لیست پیوندی به آرایه خروجی موردنظر ایجاد می شود که نشان دهنده موقعیت آن عنصر در آرایه خروجی است. [ ۳]
یکی از داده ساختارهای پرکاربرد برای ذخیره سازی مجموعه ای از اطلاعات که به طور پیوسته به روزرسانی می شود یا به آن اطلاعات جدیدی اضافه می شود، درخت فنویک است. درخت فنویک مجموع چند عدد اول یک آرایه، به همراه به روزرسانی کردن عناصر آن آرایه را در مرتبه زمانی ( O ( logn انجام می دهد. این درخت برای محاسبهٔ مجموع چند عدد اول یک آرایه به همراه به روزرسانی، از جمع پیشوندی استفاده می کند. [ ۴]
این نوشته برگرفته از سایت ویکی پدیا می باشد، اگر نادرست یا توهین آمیز است، لطفا گزارش دهید: گزارش تخلفy 0 = x 0
y 1 = x 0 + x 1
y 2 = x 0 + x 1 + x 2
. . .
برای نمونه، به جدول زیر توجه کنید.
همچنین می توان با درنظرگرفتن y 0 = x 0 , y i را با استفاده از فرمول y i = y i − 1 + x i بدست آورد. علی رغم سادگی در پیاده سازی، جمع پیشوندی در الگوریتم های خاص همچون مرتب سازی شمارشی، در زبان های برنامه نویسی تابعی در تشکیل پایه ای برای اسکن توابع مرتبه بالا و در الگوریتم های موازی مورد مطالعه قرار گرفته است. زمان صرف شده برای محاسبهٔ جمع پیشوندی از مرتبهٔ ( O ( n می باشد، حافظه ای که برای ساختن آن صرف می شود نیز ( O ( n می باشد اما در جمع پیشوندی موازی می توان حافظهٔ استعمال شده را به ( O ( logn کاهش داد.
نحوه پیاده سازی جمع پیشوندی در زبان های جاوا، پایتون و سی {به انگلیسی:به ترتیب:C, python, java} نشان داده شده است.
int* prefixSums ( int input, int output, int length ) { output = input; int i; for ( i = 1; i < length; i++ ) output = output + input; return output; پیاده سازی با کد جاوا static int prefixSums ( int input, int output ) { output = input; for ( int i = 0; i < input. length; i++ ) output = output + input; return output; } پیاده سازی پایتون def prefixSums ( input, output ) : output = input; for i in range ( 1, len ( input ) ) : output = output + input کاربردها مرتب سازی شمارشی گونه ای از مرتب سازی های خطی است که بدون مقایسه، عمل مرتب سازی عناصر یک آرایه را انجام می دهد. در مرتب سازی شمارشی، از جمع پیشوندی برای یافتن جایگاه هر عنصر در آرایه مرتب شده، استفاده می شود. [ ۲]
در رتبه بندی لیست ها، برای تبدیل یک لیست پیوندی به یک آرایه خروجی، از جمع پیشوندی استفاده می شود بدین نحو که یک آرایهٔ ورودی از ۱ها به اندازه طول لیست پیوندی ساخته می شود سپس با استفاده از جمع پیشوندی این آرایه، اندیس متناظر برای نگاشتن هر عنصر در لیست پیوندی به آرایه خروجی موردنظر ایجاد می شود که نشان دهنده موقعیت آن عنصر در آرایه خروجی است. [ ۳]
یکی از داده ساختارهای پرکاربرد برای ذخیره سازی مجموعه ای از اطلاعات که به طور پیوسته به روزرسانی می شود یا به آن اطلاعات جدیدی اضافه می شود، درخت فنویک است. درخت فنویک مجموع چند عدد اول یک آرایه، به همراه به روزرسانی کردن عناصر آن آرایه را در مرتبه زمانی ( O ( logn انجام می دهد. این درخت برای محاسبهٔ مجموع چند عدد اول یک آرایه به همراه به روزرسانی، از جمع پیشوندی استفاده می کند. [ ۴]
wiki: جمع پیشوندی