2022.1.6 时间复杂度及简单排序算法

2022.1.6 时间复杂度及简单排序算法

1. 时间复杂度

• 定义：在常数操作数量的表达式中，除去低阶项和高阶项的系数所剩下来的东西，记作O(剩下)，读作 big O(剩下)，时间复杂度按照算法执行的最差情况估计;

• 评价一个算法流程的好坏，先看时间复杂度的指标，然后再分析不同数据样本下的* 实际运行时间 *，也就是”常数运行时间“。

2. 简单排序算法

（1）选择排序

• 从数组下标为零的位置（比较的数）开始，依次与后面n-1个数（被比较的数）进行比较，找到最小的数并放在比较的数。

• 代码：

?
public class selectionSoft {
    public static void main(String[] args)
    {
        int[] arr = {4,6,2,9,4,8,6,4,5,7,1};
        SelectionSoft(arr);
    }
    
    public static void SelectionSoft(int[] arr)
    {
        for(int i=0;i<arr.length;i++)
        {
            for(int j=i+1;j<arr.length;j++)
            {
                if(arr[j]<arr[i])
                {
                    int temp = arr[i];
                    arr[i] = arr[j];
                    arr[j] = temp;
                }
            }
        }
        for(int i:arr)
        {
            System.out.print(i+" ");
        }
    }
}
?
?

• 运行结果：

  4. 二分详解

  （1）二分查找 O(logn)（在有序数组里查找某个数是否存在）

      public static void BinarySoft(int[] arr,int x)
      {
          int min = 0,max = arr.length;
          while(min<max)
          {
              int mid  = (min+max)/2;
              if(x==arr[mid])
              {
                  System.out.println(mid);
                  return;
              }
  ?
              else if(x<arr[mid])
              {
                  max = mid;
              }
              else
              {
                  min = mid;
              }
          }
      }

  (2) 在一个有序数组中，找>=某个数最左侧的位置

  public static void main(String[] args)
  {
  int[] arr = {2,4,4,4,6,7,7,8,8,9,9};
  BinarySoft(arr,4);
  }

  public static void BinarySoft(int[] arr,int x)
  {
  int min = 0,max = arr.length;
  int flag = 0;
  while(min {
  int mid = (min+max)/2;
  if(x==arr[mid])
  {
  flag = mid;
  if(arr[flag-1] break;
  else
  max = mid;
  }

  else if(x {
  max = mid;
  }
  else
  {
  min = mid;
  }
  }
  System.out.print(flag-1);
  }

  (3) 局部最小值问题