时间复杂度分析

影响程序运行的总时间主要和两点有关

执行每条语句的耗时
执行每条语句的频率

前者主要取决于计算机性能、编译器、操作系统；

后者主要取决于程序本身和输入。

大O表示法：描述算法的运行时间和数据结构规模的关系

O(1) O(n) O(log n) O(n log n) O(n^2)

例子：数组末尾添加，四条语句执行时间，O(1)

      /// <summary>
      /// index的位置插入item值
      /// </summary>
      /// <param name="index"></param>
      /// <param name="item"></param>
public void Insert(int index, T item)
      {//插入
          if (index < 0 || index > count)//----------------1
          {
              throw new ArgumentException("数组索引越界");
          }
          if (count == data.Length)//----------------------1
          {
              //throw new ArgumentException("数组已满");
              ResetCapacity(2 * data.Length);//数组扩容加原来两倍
          }
          for (int i = count - 1; i >= index; i--)//-------不成立
          {
              data[i + 1] = data[i];
          }
          data[index] = item;//----------------------------1
          count++;//---------------------------------------1
      }
      /// <summary>
      /// 末尾添加，count:元素个数
      /// </summary>
      /// <param name="item"></param>
      public void AddLast(T item)
      {
          Insert(count, item);
      }

数组头部添加,4+n条语句执行,O(n)

      /// <summary>
      /// index的位置插入item值
      /// </summary>
      /// <param name="index"></param>
      /// <param name="item"></param>
public void Insert(int index, T item)
      {//插入
          if (index < 0 || index > count)//----------------1
          {
              throw new ArgumentException("数组索引越界");
          }
          if (count == data.Length)//----------------------1
          {
              //throw new ArgumentException("数组已满");
              ResetCapacity(2 * data.Length);//数组扩容加原来两倍
          }
          for (int i = count - 1; i >= index; i--)//-------n
          {
              data[i + 1] = data[i];
          }
          data[index] = item;//----------------------------1
          count++;//---------------------------------------1
      }        

/// <summary>
      /// 头部添加
      /// </summary>
      /// <param name="item"></param>
      public void AddFirst(T item)
      {
          Insert(0, item);
      }

数组根据值找索引 O(1)或者O(n)

/// <summary>
/// 根据值找索引
/// </summary>
/// <param name="value"></param>
/// <returns></returns>
public int IndexOf(T value)
{
    for (int i = 0; i < count; i++)
    {
        if (data[i].Equals(value))//不能用==,因为都是值类型,不合法
        {//确定指定的对象是否等于当前对象。
            return i;
        }
    }
    return -1;//值不存在
}

元素存在数组中
- 元素在数组头部找到:O(1)
- 元素在数组尾部找到:O(n)
- 平均在数组中间找到:O(2/n)=O(n)
元素不在数组中:O(n)

数组末尾删除,O(1)

      /// <summary>
      /// 删除index位置的值
      /// </summary>
      /// <param name="index"></param>
      /// <returns></returns>
public T Delete(int index)
      {
          if (count == data.Length / 4)//不足四分之一时,空间减少------1
          {
              ResetCapacity(data.Length / 2);
          }
          if (index < 0 || index >= count)
          {
              throw new ArgumentException("索引超出数组界限");
          }
          T temp = data[index];//----------------------------------1
          for (int i = index + 1; i < count; i++)//不满足条件
          {
              data[i - 1] = data[i];//左移
          }
          count--;//-----------------------------------------------1
          data[count] = default(T);//------------------------------1
          return temp;//-------------------------------------------1
      }

      /// <summary>
      /// 删除末尾
      /// </summary>
      /// <returns></returns>
      public T RemoveLast()
      {
          return Delete(count - 1);
      }