پیچدگی زمانی قطعه کد زیر چقدر است؟ [بایگانی]

sayanpro

یک شنبه 17 اسفند 1399, 14:34 عصر

سلام. دوستان وقت بخیر.
شما می دونید پیچیدگی زمانی قطعه کد زیر چقدر است؟

for (i=1; i<=n; i*2)
++x;

ممنون از راهنمایی شما.

the king

یک شنبه 17 اسفند 1399, 19:13 عصر

سلام. دوستان وقت بخیر.
شما می دونید پیچیدگی زمانی قطعه کد زیر چقدر است؟

for (i=1; i<=n; i*2)
++x;

ممنون از راهنمایی شما.

عبارت سوم اون حلقه for ایراد داره، i*2 هیچ تغییری روی مقدار i ایجاد نمی کنه، به همین جهت با شرط اینکه x++ عمل اصلی باشه، برای هر n>=1 حلقه بی پایان ئه و پیچیدگی این کد بینهایت ئه، یعنی ارتباطی با مقدار n نداره.

اما اگر ;for (i=1; i<=n; i*=2) ++x بود، پیچیدگی اش 1+(n)Log2 میشه (لگاریتم مبنای 2 ئه n به علاوه 1)