سوال ۱:اگر داشته باشیم : [tex]f(n)=o(g(n)))[/tex]
کدامیک صحیح نیست:
۱)[tex]lim(n \to \infty ) \frac{f(n)}{g(n)}=0[/tex]
۲)[tex]\left \{ {\exists n_{0},c>0,\forall n>n_{0},f(n)<cg(n)} \right \}[/tex]
۳)[tex]f(n)\neq \theta (g(n)) &f(n)=O(g(n))[/tex]
۴)[tex]f(n)\neq \theta (g(n)),g(n)=\omega (f(n))[/tex]
سوال ۲:پیچیدگی زمانی اجرای تابع بازگشتی مقابل کدامست؟
function fun(n:integer)
begin
if n=1 then return(1)
else return(fun(n-1)+fun(n-1))
end
۱) O(n)
۲)[tex]O(n^{2})[/tex]
۳)[tex]O(2^{n})[/tex]
۴)[tex]O(n^{2}logn)[/tex]
سوال۳:تعداد گامهای برنامه زیر کدامست:
function mul(n:integer)real;
var t,x:real:i:integer;
begin
t:=1;
for i:=1 to n do
begin
read(x);
t:=t*x;
end;
mul:=t;
end
۱)۳n+3
۲)۲n+3
۳)۲n+1
۴)۲n
