shahmohammadi
دوشنبه 20 آذر 1391, 22:27 عصر
سلام به همه‌ي دوستان.
در يك مقاله كه يك الگوريتم موازي براي مساله‌اي ارائه داده يه چنين چيزي نوشته:
we show how to build the convex hulls of n pre-sorted points in the plane in O(1) time using O(nlogn) work:متفکر:, with n-exponential probablity:متعجب:, or alternatively, in O(logn) time using O(n) work, with n-exponential probablity.
(ترجمش نكردم چون مثل خيلي از دوستان با اصطلاحات فارسي‌ش آشنا نبودم.)
يه چيزايي در مورد پيچيدگي الگوريتم هاي موازي از كتاب بهروز پرهامي خوندم.
منظور از پيچيدگي كار (Work) چي هست؟
ديگه اين احتمال اين وسط چي كاره‌ست؟
با اين پيچيدگي كاري كه اين الگوريتم داره (اوليش) يعني nlogn يعني به اون تعداد بايد پردازنده داشته باشيم. و يعني براي يك كامپيوتر 4هسته‌اي الگوريتمي با زمان غير ثابت و پيچيدگي كار بهتر سريعتر از اين الگوريتم جواب مي‌ده؟ و نيز اين الگويتم آيا هر چقدر تعداد پردازنده ها بيشتر بشه نتيجه اش بهتر (در مقايسه با ساير الگوريتم ها) مي‌شه؟
در يك مقاله كه يك الگوريتم موازي براي مساله‌اي ارائه داده يه چنين چيزي نوشته:
we show how to build the convex hulls of n pre-sorted points in the plane in O(1) time using O(nlogn) work:متفکر:, with n-exponential probablity:متعجب:, or alternatively, in O(logn) time using O(n) work, with n-exponential probablity.
(ترجمش نكردم چون مثل خيلي از دوستان با اصطلاحات فارسي‌ش آشنا نبودم.)
يه چيزايي در مورد پيچيدگي الگوريتم هاي موازي از كتاب بهروز پرهامي خوندم.
منظور از پيچيدگي كار (Work) چي هست؟
ديگه اين احتمال اين وسط چي كاره‌ست؟
با اين پيچيدگي كاري كه اين الگوريتم داره (اوليش) يعني nlogn يعني به اون تعداد بايد پردازنده داشته باشيم. و يعني براي يك كامپيوتر 4هسته‌اي الگوريتمي با زمان غير ثابت و پيچيدگي كار بهتر سريعتر از اين الگوريتم جواب مي‌ده؟ و نيز اين الگويتم آيا هر چقدر تعداد پردازنده ها بيشتر بشه نتيجه اش بهتر (در مقايسه با ساير الگوريتم ها) مي‌شه؟