2019年1月

将存有n个人的电话簿按照人名排序,时间复杂度是多少?

每次需要检查元素中n个元素,需要的时间为O(n)。这样的操作需要操作n次,所以时间复杂度为O(n x n),即O (n 2 )。
但实际上第一次需要检查n 个元素,但随后检查的元素数依次为n - 1, n – 2, …, 2和1。平均每次检查的元素数为1/2 × n ,因此运行时间为O (n × 1/2 × n )。但大O表示法省略诸如1/2这样的常数,因此简单地写作O(n x n)。

选择排序原理

在要排序的一组数中,选出最小的一个数与第一个位置的数交换。然后在剩下的数当中再找最小的与第二个位置的数交换,如此循环到倒数第二个数和最后一个数比较为止。

选择排序代码实现

 /**
  * 选择排序.
  *
  * @param  array $value 待排序数组
  *
  * @return array
  */
  function select_sort(&$value=[])
  {
    $length = count($value)-1;
    for ($i=0; $i < $length; $i++) {
      $point = $i;// 最小值索引
      for ($j=$i+1; $j <= $length; $j++) {
        if ($value[$point] > $value[$j]) {
          $point = $j;
        }
      }
      $tmp = $value[$i];
      $value[$i] = $value[$point];
      $value[$point] = $tmp;
    }
    return $value;
  }

冒泡排序原理

在要排序的一组数中,对当前还未排好的序列,从前往后对相邻的两个数依次进行比较和调整,让较大的数往下沉,较小的往上冒。即,每当两相邻的数比较后发现它们的排序与排序要求相反时,就将它们互换。

冒泡排序代码实现


  /**
   * 冒泡排序
   * bubble sort algorithm
   * 
   * @param  array $value 待排序数组 the array that is waiting for sorting
   * @return array
   */
  function bubble($value = [])
  {
      $length = count($value) - 1;
      // 外循环
      // outside loop
      for ($j = 0; $j < $length; ++$j) {
          // 内循环
          // inside loop
          for ($i = 0; $i < $length; ++$i) {
              // 如果后一个值小于前一个值,则互换位置
              // if the next value is less than the current value, exchange each other.
              if ($value[$i + 1] < $value[$i]) {
                  $tmp = $value[$i + 1];
                  $value[$i + 1] = $value[$i];
                  $value[$i] = $tmp;
              }
          }
      }
      return $value;
  }
  /**
   * 优化冒泡排序
   * optimized bubble sort algorithm
   * 
   * @param  array $value 待排序数组 the array that is waiting for sorting
   * @return array
   */
  function bubble_better($value = [])
  {
    $flag   = true; // 标示 排序未完成 the flag about the sorting is whether or not finished.
    $length = count($value)-1; // 数组最后一个元素的索引 the index of the last item about the array.
    $index  = $length; // 最后一次交换的索引位置 初始值为最后一位 the last exchange of index position, default value is equal to the last index.
    while ($flag) {
      $flag = false; // 假设排序已完成 let's suppose the sorting is finished.
      for ($i=0; $i < $index; $i++) {
        if ($value[$i] > $value[$i+1]) {
          $flag  = true; // 如果还有交换发生,则排序未完成  if the exchange still happen, it show that the sorting is not finished. 
          $last  = $i; // 记录最后一次发生交换的索引位置 taking notes the index position of the last exchange.
          $tmp   = $value[$i];
          $value[$i] = $value[$i+1];
          $value[$i+1] = $tmp;
        }
      }
      $index = !$flag ? : $last;
    }
    return $value;
  }

内存的工作原理

有一个存储柜,存储柜有很多抽屉,每个抽屉均有自己的编号:fe0ffeeb(一个内存单元的地址),每个抽屉可以放一样东西。现在你要存两样东西,因此你向柜台要了两个抽屉(需要将数据存储到内存时,你请求计算机提供存储空间,计算机给你一个存储地址)。

用数组还是链表?

有时候,需要在内存中存储一系列元素。假设你要编写一个管理待办事项的应用程序,为此需要将这些待办事项存储在内存中。应使用数组还是链表呢?

数组

数组的特点:

  • 数组中的每个元素在内从中都是相连的
  • 数组的元素带编号,编号从0开始

鉴于数组更容易掌握,我们先将待办事项存储在数组中。使用数组意味着所有待办事项在内存中都是相连的(紧靠在一起的)。现在我们有四个代办事项,要放在抽屉,但是后面的抽屉被别人占用了。

1547023972659.jpg

就像是占连在一排的座位,原来的四连坐有一个位置被占了,我们只能另找座位(数组在存储或者新增元素时如果没了空间,就得移到内存其他地方)。
基于数组连在一起的缺点,我们可以”预留座位“,但是这样做也有缺点:

  • 你额外请求的位置可能根本用不上,这将浪费内存。你没有使用,别人也用不了。
  • 待办事项超过10个后,你还得转移。

鉴于这种情况,我们使用链表!

链表

链表有两个特点:

  • 链表中的元素可存储在内存的任何地方。
  • 链表的每个元素都存储了下一个元素的地址,从而使一系列随机的内存地址串在一起。

这犹如寻宝游戏。你前往第一个地址,那里有一张纸条写着“下一个元素的地址为123”。因此,你前往地址123,那里又有一张纸条,写着“下一个元素的地址为847”,以此类推。在链表中添加元素很容易:只需将其放入内存,并将其地址存储到前一个元素中。

两者优劣点

  • 链表存在类似的问题。在需要读取链表的最后一个元素时,你不能直接读取,因为你不知道它所处的地址,必须先访问元素#1,从中获取元素#2的地址,再访问元素#2并从中获取元素#3的地址,以此类推,直到访问最后一个元素。需要同时读取所有元素时,链表的效率很高:你读取第一个元素,根据其中的地址再读取第二个元素,以此类推。但如果你需要跳跃,链表的效率真的很低。
  • 数组与此不同:你知道其中每个元素的地址。例如,假设有一个数组,它包含五个元素,起始地址为00,那么元素#5的地址是多少呢?

数组和链表操作的运行时间

-数组链表
读取O(1)O(n)
插入O(n)O(1)
删除O(n)O(1)