专栏首页take time, save time你所能用到的数据结构(一)

你所能用到的数据结构(一)

     无损编码的霍夫曼编码以及其余的各种编码由于要使用比较复杂的数据结构,所以按照我昨天说的,我决定从数据结构开始写起。数据结构和算法很难完全的分开,好的数据结构能够提升算法的效率,而如果没有算法,单纯的谈数据结构,那么数据结构的应用价值就会大大的降低。那么,就从最基本的开始这一个系列吧。

一、总是让人很抽象的算法分析

算法分析基本是所有数据结构与算法的第一章要讲的内容,大0表示法什么的总是让人很抽象,对于初学者,其实这一章的意义并不是很大,因为你很遇到在实际开发中一些大数据集的问题,在小规模数据的时候,各个算法之间的差别很难分辨出来。这就好比计算5个数的和,大家所用的时间基本都会差不多,但是要是计算5000个数的和,那么天才和一般人之间的差距就会体现出来了,这也就是为什么对于一个大型企业,一个人才远远比10个干事的人重要的原因。

     算法分析的还有一个作用就是让学计算机的明白,计算机虽然快,但是计算机不是万能的,计算机再牛逼也不能很容易的就处理成万上亿的数据的。比如说我们用的QQ,虽然经常说腾讯抄袭,网络即时通信软件但从技术上来说不是特别难,难的是几千万人同时在线一点也不开,你的好友下线了,你马上就能收到通知,这一点不是很容易就能做到的。反例就是铁道部的订票网站,为什么经常崩溃,被万人辱骂,算法和优化的失败就是很大的原因。优化是商业软件一个永恒的主题,如果在最初学习的时候能有这样一个概念,我相信对于以后是有很大帮助的。

     下面来说说大O表示法吧,从O(N)说起,不说那些算法时间复杂度上界什么什么的,如果你对这个有兴趣的话,可以查阅一下算法的书籍,我觉得这个东西最简单的理解方式就是利用循环,对于一个循环从1到N,然后对一个数组a赋值,也就是for(int i=0;i<N;i++) a[i]=i; 那么你就可以把这个理解为时间复杂度是O(N),所谓的N是问题的规模,也就是说对于这个算法,算法所消耗的时间随着规模的增大而增大,比如现在处理1万个数据需要0.1s,那么长到2万个就需要0.2s。

     对于其他的大O表示法的问题基本都可以按照这个方法类推,对于一个算法能达到O(N)已经是非常非常牛逼的,极个别的比如二分查找可以达到很快的速度,但是不能忽视它前面的需要进行排序预处理。如果对于一个排序算法,按照一个人的正常思维,首先,你需要将待排序的所有数浏览一遍,然后才能确定哪个大哪个小,这样才能进行排序,如此一来对于一组待排序的数,你需要浏览两遍数组才能完成,那么这个人眼扫描算法的效率就是O(N*N)的。

     为了直观的显示效率的意义,按照我写这一系列文章重点一定要突出实际的编程,采用C++写了一段程序来显示随着规模的增长,冒泡和快速算法所用的时间的增长,为了对比,加入了空白对照组,先展示结果吧。

     第一行和第二行是两个空循环,可以看到,第二行的数据规模是第一行的两倍,其处理时间也差不多是两倍,也就是算法复杂度是O(N)。

     第三行和第四行分别是两个不同规模的冒泡排序,冒泡排序算法复杂度是O(N*N),可以看到第三行是第四行处理速度大约4倍。

     第五行和第六行分别是两个不同规模的快速排序,快速排序的算法复杂度是O(N*LogN),至于为什么,放在后面的文章中再分析。

     N*LogN这个是非常小的,所以最后两行所耗费的时间差不多,从这三组数据可以看出一个好的算法对于一个软件的运行速度影响之大,一个冒泡算法处理30000个数据时快速排序处理100000的将近40倍,所以说算法可以说是衡量一个工程师好与坏的重要标准。

     下面贴出所有代码,clock函数是用来计时的, 这里要提出的一点是这里的冒泡和快速排序算法不是我写的,都是复制的,毕竟目前介绍的重点还不是这个,另外这个快速排序是标准里面的,很有参考学习价值。

  1 int main()
  2 {
  3     const long int num=100000;
  4   
  5   clock_t begin, end;
  6   double  cost;
  7 
  8   int dat[num];
  9   srand( (unsigned int)time(0) );
 10   for (int i = 0; i < 30000; i++){
 11        dat[i] = rand();
 12   }
 13   begin = clock();
 14   for(int loop=0;loop<10000000;loop++);
 15   end = clock();
 16   cost = (double)(end - begin) / CLOCKS_PER_SEC;
 17   cout<<"loop for 10000000 values:"<<cost<<"seconds\n"; 
 18 
 19   begin = clock();
 20   for(int loop=0;loop<20000000;loop++);
 21   end = clock();
 22   cost = (double)(end - begin) / CLOCKS_PER_SEC;
 23   cout<<"loop for 20000000 values:"<<cost<<"seconds\n"; 
 24 
 25    
 26   bubble(dat,30000);
 27   
 28   srand( (unsigned int)time(0) );
 29   for (int i = 0; i < 15000; i++){
 30        dat[i] = rand();
 31   }
 32 
 33   bubble(dat,15000);
 34   
 35 
 36   srand( (unsigned int)time(0) );
 37   for (int i = 0; i < 100000; i++){
 38        dat[i] = rand();
 39   }
 40 
 41   begin = clock();
 42   quickSort(dat,100000);
 43   end = clock();
 44   cost = (double)(end - begin) / CLOCKS_PER_SEC;
 45   cout<<"qsort for 1000000 values:"<<cost<<"seconds\n"; 
 46 
 47     
 48    srand( (unsigned int)time(0) );
 49   for (int i = 0; i < 50000; i++){
 50        dat[i] = rand();
 51   }
 52   begin = clock();
 53   quickSort(dat,50000);
 54   end = clock();
 55   cost = (double)(end - begin) / CLOCKS_PER_SEC;
 56   cout<<"qsort for 500000 values:"<<cost<<"seconds\n"; 
 57   int i;
 58   cin>>i;
 59   return 0;
 60 }
 61 
 62 void quickSort(int numbers[], int array_size)
 63 {
 64   q_sort(numbers, 0, array_size - 1);
 65 }
 66 
 67 
 68 
 69 void q_sort(int numbers[], int left, int right)
 70 {
 71   int pivot, l_hold, r_hold;
 72 
 73   l_hold = left;
 74   r_hold = right;
 75   pivot = numbers[left];
 76   while (left < right)
 77   {
 78     while ((numbers[right] >= pivot) && (left < right))
 79       right--;
 80     if (left != right)
 81     {
 82       numbers[left] = numbers[right];
 83       left++;
 84     }
 85     while ((numbers[left] <= pivot) && (left < right))
 86       left++;
 87     if (left != right)
 88     {
 89       numbers[right] = numbers[left];
 90       right--;
 91     }
 92   }
 93   numbers[left] = pivot;
 94   pivot = left;
 95   left = l_hold;
 96   right = r_hold;
 97   if (left < pivot)
 98     q_sort(numbers, left, pivot-1);
 99   if (right > pivot)
100     q_sort(numbers, pivot+1, right);
101 }
102 
103 void bubble(int a[],int length)
104 {
105     
106    clock_t begin, end;
107   double  cost;
108     int temp;
109 
110     begin = clock();
111     for(int j=0;j<=length-1;j++)
112     { 
113        for (int i=0;i<length-j;i++)
114         if (a[i]>a[i+1])
115         { 
116             temp=a[i];
117             a[i]=a[i+1];
118             a[i+1]=temp;
119         }
120     }
121     end = clock();
122    cost = (double)(end - begin) / CLOCKS_PER_SEC;
123    cout<<"bubble for "<<length<<" values:"<<cost<<"seconds\n"; 
124     
125 } 

      我写的“你所能用到的”这个系列,重点在于实现,如果你需要补充各种知识,请参考一些书籍,我一直的观点是编程就像游泳一样,游泳重要的是要下水试而不是什么游泳理论,当你学会了游泳之后,游泳理论可以帮你快速提高,但如果只会游泳理论,你是永远也不会游泳,所以我的系列里保证所有贴出的代码是一定都能用的,能运行处结果的,这样对于初学者是一个成就感的反馈。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 你所能用到的数据结构(四)

    五、如何递,怎样归? 很多人看完递归的原理之后会有这种感觉,喔,这个原理我懂了,然后再找一道其余的题目看一看能不能写的出来,突然发现,我勒个去,还是不会。其实...

    一心一怿
  • Think in 递归

         网上写递归的文章可以用汗牛充栋来形容了,大多数都非常清晰而又细致的角度上讲解了递归的概念,原理等等。以前学生的时候,递归可以说一直是我的某种死穴,原理...

    一心一怿
  • 你所能用到的数据结构(二)

          周末开始更新了,首先感谢各位对我写的东西还能保持兴趣,先回答几个留言中的一个问题和我对无损编码那一节的一个留言的一个看法,第一个是推荐算法书,首先,...

    一心一怿
  • 算法:快速排序以及第k小元素的线性选择算法

    简要介绍下快速排序的思想:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行...

    s1mba
  • 漫画:滑动窗口系列 第二讲(无重复字符的最长子串)

    在上一节中,我们使用双端队列完成了滑动窗口的一道颇为困难的题目,以此展示了什么是滑动窗口。在本节中我们将继续深入分析,探索滑动窗口题型一些具有模式性的解法。

    程序员小浩
  • 根据达尔文进化论,只有最强人工智能算法才能生存

    国际财经媒体Quartz报道,据谷歌和美国“开放人工智能实验室”(OpenAI)的一项研究,类达尔文进化论的神经进化理论可以帮助人工智能算法进化优化。 现代人工...

    人工智能快报
  • 外部存档指导的多目标进化算法简略版

    正值毕业季,小编这里简洁明了地讲述一下自己毕业设计相关的算法。 当初之所以跟着导师学习进化算法,首先很有意思的一点是,进化算法是一种种群类算法,设计算法思路的时...

    智能算法
  • 【产品动态】关于2019年8月19日智能钛机器学习平台系统升级通知

           您好!为了给您提供更好的服务,我们将于2019年8月19日升级智能钛机器学习平台系统,预计维护时间为19:00至22:00。期间平台暂时无法使用,...

    腾讯智能钛AI开发者
  • 数据结构(一)

    所有程序员必不可少的基础就是数据结构与算法,这也是我们在未来面试中必不可少的考点和加分点。

    可爱见见
  • 手把手:AlphaGo有啥了不起,我也能教你做一个(附Python代码)

    大数据文摘

扫码关注云+社区

领取腾讯云代金券