mohammadpmf
شنبه 12 فروردین 1391, 19:11 عصر
با سلام خدمت همه ی دوستان عزیز،
مشکلی که میخوام مطرح کنم مربوط به الگورتم نویسی هست.
یه برنامه ای هست که به این قراره:
ابتدا کاربر n (حداکثر100000) عدد صحیح به برنامه میده.
بعد از وارد کردن این اعداد. قراره که q (حداکثر 100000) سوال از برنامه پرسیده بشه که سوالاتش به یکی از این دو صورت هست.
1- مجموع اعداد از شماره ی آیُم تا جیُم رو حساب کن.
2- ماکزیمم اعداد از شماره ی آیُم تا جِیُم رو حساب کن.
راه حل اولش که همه به ذهنشون میرسه اینه که هر 2 نوع سوال رو با یه for حساب کنیم.
ولی این هزینش O(n) هست و وقتی q بار هم پرسیده بشه، میشه O(n*q) که تو این مثال میشه 10000000000 عملیات و الگوریتم خوبی نیست.
میخواستم بدونم چه طور میشه این کار رو در O(nlogn) انجام داد.
با تشکر.
مشکلی که میخوام مطرح کنم مربوط به الگورتم نویسی هست.
یه برنامه ای هست که به این قراره:
ابتدا کاربر n (حداکثر100000) عدد صحیح به برنامه میده.
بعد از وارد کردن این اعداد. قراره که q (حداکثر 100000) سوال از برنامه پرسیده بشه که سوالاتش به یکی از این دو صورت هست.
1- مجموع اعداد از شماره ی آیُم تا جیُم رو حساب کن.
2- ماکزیمم اعداد از شماره ی آیُم تا جِیُم رو حساب کن.
راه حل اولش که همه به ذهنشون میرسه اینه که هر 2 نوع سوال رو با یه for حساب کنیم.
ولی این هزینش O(n) هست و وقتی q بار هم پرسیده بشه، میشه O(n*q) که تو این مثال میشه 10000000000 عملیات و الگوریتم خوبی نیست.
میخواستم بدونم چه طور میشه این کار رو در O(nlogn) انجام داد.
با تشکر.