TOP

c++数据结构笔记01(二)
2019-09-06 00:26:19 】 浏览:61
Tags:数据结构 笔记

的含义,不会出现二义性

       可行性:算法的每一步都是可行的

算法效率的度量

  1. 事后统计法

比较不同算法对同一组输入数据的运行处理时间

              缺陷

                     为了获得不同算法的运行时间必须编写相应程序

                     运行时间严重依赖硬件以及运行时间的环境因素

                     算法的测试数据的选取相当困难

              事后统计法虽然直观,但是实施困难且缺陷多

  1. 事前分析估算

依据统计的方法对算法效率进行估算

影响算法效率的主要因素

       算法采用的策略和方法

       问题的输入规模

       编译器所产生的代码

       计算机执行速度

       判断一个算法的效率时,往往只需要关注操作数量的最高次项,其它次要项和常数项可以忽略。

       在没有特殊说明时,我们所分析的算法的时间复杂度都是指最坏时间复杂度。

大O表示法

       算法效率严重依赖于操作(Operation)数量

       在判断时首先关注操作数量的最高次项

       操作数量的估算可以作为时间复杂度的估算

      

       O(5) = O(1)

       O(2n+1) = O(2n) = O(n)

  O(n2+n+1) = O(n2)

  O(3n3+1) = O(3n3) = O(n3)

常见时间复杂度

执行次数函数

非正式术语

12

O(1)

常数阶

2n+3

O(n)

线性阶

3n2+2n+1

O(n2)

平方阶

5log2n + 20

O(logn)

对数阶

2n+3nlog2n+19

O(nlogn)

nlogn阶

6n3+2n2+3n+4

O(n3)

立方阶

2n

O(2n)

指数阶

 一般的关系:

O(1)< O(logn)< O(n)< O(nlogn)< O(n2)< O(n3)< O(2n)<O(n!)<O(nn) 

 

 1 //此次代码在codeblocks 17.12 下成功运行
 2 #include <iostream>
 3 
 4 using namespace std;
 5 //时间换空间
 6 /*
 7     问题:
 8     在一个由自然数1-1000中某些数字所组成的数组中,每个数字可能出现零次
 9     或者多次。设计一个算法,找出出现次数最多的数字
10 */
11 
12 void Search(int *a, int len);
13 
14 int main()
15 {
16     int ary[] = {1,1,2,8,8,8,9,4,4,5,6,7,9,9,9,9};
17     Search(ary,sizeof(ary)/sizeof(*ary));
18     return 0;
19 }
20 
21 void Search(int *a, int len)
22 {
23     int sp[1000] = {0};
24     int i = 0;
25     int Max = 0;
26 
27     //将数组中的值减1赋给另外一个数组的索引即下标
28     for(i=0; i<len; i++)
29     {
30         int index=a[i]-1;
31         sp[index]++;  //计算每个数字出现的次数
32     }
33 
34     //在新的数组空间内找出最大的次数
35     for(i=0; i<1000; i++)
36     {
37         if(Max < sp[i])
38         {
39             Max = sp[i];
40         }
41     }
42 
43     //输出出现最多次数的数字
44     for(i=0; i<1000; i++)
45     {
46         if(Max == sp[i])
47         {
48             //cout << "数字出现最多的次数为 " << Max << endl;
49             cout << "出现次数最多的数字为 " << i+1 << endl;
50         }
51     }
52 }

 


c++数据结构笔记01(二) https://www.cppentry.com/bencandy.php?fid=49&id=250184

首页 上一页 1 2 下一页 尾页 2/2/2
】【打印繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部
上一篇201803-2 碰撞的小球 下一篇矩阵乘法(五):置换