مرتبه زمانی این کد رو چطور حساب کنم؟

[ali_orz]

int j = 1;
while( j <= n)
{
x++;
j = k * j;
}

[IamOverlord]

خوب بستگی داره k چی باشه...

[مسعود اقدسی فام]

int j = 1;
while( j <= n)
{
x++;
j = k * j;
}

لگاریتم n در مبنای k

[مسعود اقدسی فام]

لگاریتم n در مبنای k

در هر بار تکرار حلقه مقدار j، ضرب در k می‌شه. یعنی k برابر می‌شه. یعنی اول k، بعد k * k = k2، بعد k3، ... تا زمانی که kp > n بشه. در این حالت حلقه p بار اجرا شده.

p هم به صورت تخمینی برابره با لگاریتم n در مبنای k.