程式的BIG O

boxwayne444

int i,max,min;
for(i=1;i<=n;i++)
{
     if(a[i]>max)max=a[i];
     if(a[i]<min)min=a[i];
}
書上說要進行2(n-1)次比較   時間複雜度為O(n)

可是依據我的想法
int i,max,min;
for(i=1;i<=n;i++)  這裡不是n-1+1次 還要加最後一次i>n時的判斷+1   所以這行應該是n+1次
{回圈內執行n次
     if(a[i]>max)max=a[i]; 這裡判斷一次      
...

瀏覽完整內容，請先 註冊 或 登入會員

ddlao

實際上第一次是不用比較的哦，因為第一次max和min都可以直接等于a[i]。
所以說2n次和2(n-1)次都是有道理的
但是無論是2n次還是2(n-1)次，時間復雜度都是O(n)