设计求解下列问题的类C语言算法,并分析其最坏情况时间复杂性及其量级。 1.在数组A(1..n)中查找

设计求解下列问题的类C语言算法,并分析其最坏情况时间复杂性及其量级。
1.在数组A(1..n)中查找值为K的元素,若找到也输出其位置i(1<=i<=n),否则输出0作为标志。
2.找出数组A[1..n]中元素的最大值和次最大值。
(1)int locate(datatypeA [1..n], datatype k)
{ i=1;
while ( (1<=n) &&(A[i]! =k)) i++;
if(i<=n) return(i);
else return(0);
} 当查找不成功时,总是比较n+1次,所以,最坏时间复杂性为n+1。其量级T(n)=O(n)。
(2) Void CZ_max(datatype A[n],x,y)
{x=A[1]; y=A[1];
for(i=2;i<=n; i++)
if(x,A[i]) {y=x;x=A[i];}
eise if (y<A[i]) y=A[i];
} 若以条件判断语句为标准操作,则最坏情况时间复杂性为n-1。其量级为T(n)=O(n)。

思路:
最坏情况比较次数
最好情况比较次数
求出平均比较次数
算出基本运算次数
得出时间复杂度 f(n)=O(g(n))
温馨提示:答案为网友推荐,仅供参考
相似回答