算法.txt

算法分析常见简答题与常见算法 简答题.txt 算法.txt

求两个数的的公约数：

  while n≠0 do
   r=m  mod  n
   m=n
   n=r
  return m

顺序查找
  sequentiasearch(A[0...n-1],k)
  i=0
   while i<n and a[i]≠k do
    i=i+1
    if  i<n return  i
   else return -1

 改进的A[n]=k
       i=0
    while A[i]≠k do
    i=i+1
    if i<n return 1
    else return  -1


找最大值MAX
   MAX (A[0...n-1])
   max=A[0]
  for (i=1;i<n;i++)
  {if A[i]>max
      max=A[i]}
  return max
  复杂度：c(n)= 累加上n-1下i=1 ：1=n-1


验证都是唯一元素
  for (i=0;i<=n-2;i++)
  { for (j=i+1;j<=n-1;j++) 
  if A[i]=A[j] return  false}
  return  ture
  改进的，先排序后检验
    for (i=0;i<=n-2;i++)
      if A[i]=A[i+1]  return false
    return  true
分析：排序最低可用nlogn如合并排序，后者比较不超过n-1，
      所以最低可以nlogn


斐波那契数列
  fib(n)
  f[0]=0,f[1]=1
  for (i=2;i<=n;i++)
 {f[i]=f[i-1]+f[i-2]}
   return f(n)



选择排序
  for (i=0;i<=n-2;i++)
  {min=i
    for (j=i+1;j<=n-1;j++)
  {if  A[j]<A[min] ;
    min=j  }
 swap A[i] and A[min]}

  复杂度n平方


冒泡排序

   for (i=0;i<=n-2;i++)
     for (j=0;j<=n-2-i;i++)
        if A[j+1]<A[j]
   swap A[j] and A[j+1]


快速排序：

  Quicksort(A[l..r])

  if l<r
  s=Partition(A[l..r])//s是分裂位置

  Quicksort(A[l..s-1])
  Quicksort(A[s-1..r])

  Partition(A[l..r])
   p=A[l]
   i=l;j=r+1
  repeat
    repeat i=i+1 until  A[i]>=p
    repeat j=j+1 until  A[j]<=p
  swap (A[i],A[j])
  until i>=j
   swap (A[i],A[j])
   swap (A[l],A[j])
  return j



折半查找

  l=0 ; r=n-1
  while  l<=r  do
  m=(l+r)/2向下取整
  if k=A[m] return m
  else  if  k<A[m]  r=m-1
  else  l=m+1
  return  -1  

插入排序

  for (i=0;i<=n-2;i++)
   v=A[i]
   j=i-1
   while  j>=0  and  A[j]>v
     A[j+1]=A[j]
     j=j-1
     A[j+1]=v




计数排序：

  for (i=0;i<=n-1;i++)
   count[i]=0
  for (i=0;i<=n-2;i++)  
    for (j=0;j=n-1;j++)
       if A[i]<A[i]
         count[j]=count[j]+1
       else  count[i]=count[i]+1

  for (i=0;i<=n-1;i++)
    S[count[i]]=A[i]
  return S

分析，基本操作是比较，1，n(n-1)/2