vlambda博客
学习文章列表

时间复杂度

设定算法操作执行次数为函数T(n)，若存在函数f(n)，使得n趋向于无穷大时，T(n)/f(n)的极限值为不等于0的常数，建成后f(n)是T(n)的通数量级函数，记作T(n)=O(f(n)),O为算法的渐进时间复杂度，简称时间复杂度。

计算原则：

• 如果运行时间是常数量级，则用常数1表示。

• 只保留时间函数的最高阶项

• 如果最高阶项存在，则省去前面的系数

空间复杂度

空间复杂度是对一个算法在运行过程中临时占用存储空间大小的量度。S(n)=O(f(n))。

我们对之前文章七种排序列出的复杂度：

更多细节推荐文末第一篇文章。https://blog.csdn.net/yushiyi6453/article/details/76407640

另外再来介绍一种排序算法--计数排序。

假如有一系列数字90-100，现在排序。

 
   
   
 

  
    
    
  
function sort()
  
    
    
  
{
  
    
    
  
 $arr = [98, 96, 99, 90, 99, 92, 91, 94, 98, 96, 95];
  
    
    
  
 $min = $max = $arr[0];
  
    
    
  
 $count = count($arr);
  
    
    
  
 // 计算长度
  
    
    
  
 for ($i=1; $i < $count; $i++) {
  
    
    
  
 if ($arr[$i] > $max) {
  
    
    
  
 $max = $arr[$i];
  
    
    
  
 continue;
  
    
    
  
 }
  
    
    
  


  
    
    
  
 if ($arr[$i] < $min) {
  
    
    
  
 $min = $arr[$i];
  
    
    
  
 }
  
    
    
  
 }
  
    
    
  
 $length = $max - $min;
  
    
    
  


  
    
    
  
 for ($i=0; $i<=$length; $i++) {
  
    
    
  
 $countArr[$i] = 0;
  
    
    
  
 }
  
    
    
  


  
    
    
  
 //计数
  
    
    
  
 for ($i=0; $i<$count; $i++) {
  
    
    
  
 $countArr[$arr[$i] - $min]++;
  
    
    
  
 }
  
    
    
  


  
    
    
  
 //遍历回来
  
    
    
  
 foreach ($countArr as $k=>$v) {
  
    
    
  
 for ($j=0; $j<$v; $j++) {
  
    
    
  
 $result[] = $k+$min;
  
    
    
  
 }
  
    
    
  
 }
  
    
    
  


  
    
    
  
 return $result;
  
    
    
  
}
 
   
   
 

可以看看gif图片：

那么问题来了，假如这些数字是学生成绩，同分的我们也需要记下对应的人排名，那么怎么办呢？

我们可以在计数之后在进行依次遍历，在对应的下标增加进入前面下标的数量。

假定现在有:

 
   
   
 

  
    
    
  
[92, 91, 90, 95, 94, 99, 97, 99, 91, 92]
 
   
   
 

红色是普通的计数，黄色的是进阶计数。

 
   
   
 

  
    
    
  
function sort()
  
    
    
  
{
  
    
    
  
 $arr = ['a' => 92, 'b' => 91, 'c' => 90, 'd' => 95, 'e' => 94, 'f' => 99,
  
    
    
  
 'h' => 97, 'i' => 99, 'j' => 91, 'k'=>92];
  
    
    
  
 $min = $max = $arr['a'];
  
    
    
  
 $count = count($arr);
  
    
    
  
 // 计算长度
  
    
    
  
 foreach ($arr as $val) {
  
    
    
  
 if ($val > $max) {
  
    
    
  
 $max = $val;
  
    
    
  
 continue;
  
    
    
  
 }
  
    
    
  


  
    
    
  
 if ($val < $min) {
  
    
    
  
 $min = $val;
  
    
    
  
 }
  
    
    
  
 }
  
    
    
  
 $length = $max - $min;
  
    
    
  


  
    
    
  
 for ($i=0; $i<=$length; $i++) {
  
    
    
  
 $countArr[$i] = 0;
  
    
    
  
 }
  
    
    
  


  
    
    
  
 //计数
  
    
    
  
 foreach ($arr as $val) {
  
    
    
  
 $countArr[$val - $min]++;
  
    
    
  
 }
  
    
    
  
 // var_dump($countArr);
  
    
    
  
 for ($i=1; $i<=$length; $i++) {
  
    
    
  
 $countArr[$i] += $countArr[$i-1];
  
    
    
  
 } 
  
    
    
  
 //遍历回来
  
    
    
  
 foreach ($arr as $k=>$val) {
  
    
    
  
 $result[$count + 1 - $countArr[$val - $min] - 1] = [$k, $val];
  
    
    
  
 $countArr[$val - $min]--;
  
    
    
  
 }
  
    
    
  


  
    
    
  
 return $result;
  
    
    
  
}
 
   
   
 

计数排序适合排序有效区间内的整数，局限性比较多。

参考文章：

文中图片来自以下文章，如有版权问题，请告知删除。有兴趣也可以看下以下文章。

• 排序算法时间复杂度、空间复杂度、稳定性比https://blog.csdn.net/yushiyi6453/article/details/76407640
  

• 《漫画算法》@程序员小灰
  

• 时间复杂度和空间复杂度-https://www.cnblogs.com/chenjinxinlove/p/10038919.html

• 计数排序-https://www.jianshu.com/p/e9db78d3c93c

• 计数排序--《程序员小灰》- https://www.cnblogs.com/easilyai/p/9769773.html