时间复杂度计算实例

表示时间复杂度的阶有：

O(1) ：常量时间阶          O (n)：线性时间阶

O(㏒n) ：对数时间阶    O(n㏒n) ：线性对数时间阶

O (n^k)： k≥2 ，k次方时间阶

例１  两个n阶方阵的乘法

              for(i=1，i<=n; ++i)

                  for(j=1; j<=n; ++j)

                     {   c[i][j]=0 ;

                          for(k=1; k<=n; ++k)

                         c[i][j]+=a[i][k]*b[k][j] ; 

}

由于是一个三重循环，每个循环从1到n，则总次数为： n×n×n=n³　时间复杂度为T(n)=O(n³)【立方阶】

例２  {++x; s=0 ;}

将x自增看成是基本操作，则语句频度为１，即时间复杂度为Ｏ(1) 。【常量阶】

如果将s=0也看成是基本操作，则语句频度为２，其时间复杂度仍为Ｏ(1)，即常量阶。

例３   for(i=1; i<=n; ++i)

               { ++x; s+=x ; } 

语句频度为：2n，其时间复杂度为：O(n) ，即为【线性阶】。

例４   for(i=1; i<=n; ++i)

　　　　for(j=1; j<=n; ++j)

                   { ++x; s+=x ; }

   语句频度为：n*n*2=2n² ，其时间复杂度为：O(n²) ，即为【平方阶】。

定理：若A(n)=a_mn^m +a_m-1n^m-1+…+a₁n+a₀是一个m次多项式，则A(n)=O(n^m)

例５   for(i=2;i<=n;++i)

              for(j=2;j<=i-1;++j)

                    {++x; a[i,j]=x; }

语句频度为：   1+2+3+…+n-2=(1+n-2) ×(n-2)/2

=(n-1)(n-2)/2 =n²-3n+2

 ∴时间复杂度为O(n²)，即此算法的时间复杂度为【平方阶】。

一个算法时间为O(1)的算法，它的基本运算执行的次数是固定的。因此，总的时间由一个常数（即零次多项式）来限界。而一个时间为O(n²)的算法则由一个二次多项式来限界。

以下六种计算算法时间的多项式是最常用的。其关系为：

     O(1) < O(&#13266;n) < O(n) < O(n&#13266;n) < O(n²) < O(n³)

  指数时间的关系为：

    O(2ⁿ) < O(n!) < O(nⁿ)

当n取得很大时，指数时间算法和多项式时间算法在所需时间上非常悬殊。

例1：素数的判断算法。

void prime( int n)

{  

int i=2 ;

while ( (n%i)!=0 && i*1.0< sqrt(n) )  

     i++ ;

if (i*1.0>sqrt(n) )

      printf(“&d 是一个素数\n” , n) ;

else

      printf(“&d 不是一个素数\n” , n) ;

}

嵌套的最深层语句是i++；其频度由条件( (n% i)!=0 && i*1.0< sqrt(n) ) 决定，显然i*1.0< sqrt(n) ，时间复杂度O(n^1/2)。

或者说是O(sqrt(n))；

例2：冒泡排序法。

Void bubble_sort(int a[]，int n)

{  

change=false;

for (i=n-1; change=TURE; i>1 && change; --i)

for (j=0; j<i; ++j)

if (a[j]>a[j+1])

    {     a[j] ←→a[j+1] ;   change=TURE ; }

}

最好情况：0次

最坏情况：1+2+3+&#8943;+n-1=n(n-1)/2

平均时间复杂度为： O(n²)  【平方阶】                  

抽象数据类型的表示与实现

抽象数据类型(Abstract Data Type 简称ADT)是指一个数学模型以及定义在此数学模型上的一组操作。

抽象数据类型需要通过固有数据类型(高级编程语言中已实现的数据类型)来实现。抽象数据类型是与表示无关的数据类型，是一个数据模型及定义在该模型上的一组运算。

对一个抽象数据类型进行定义时，必须给出它的名字及各运算的运算符名，即函数名，并且规定这些函数的参数性质。一旦定义了一个抽象数据类型及具体实现，程序设计中就可以像使用基本数据类型那样，十分方便地使用抽象数据类型。

抽象数据类型的描述包括给出抽象数据类型的名称、数据的集合、数据之间的关系和操作的集合等方面的描述。

【通俗的说：就是名字、数据集合、关系和操作的集合】

抽象数据类型描述的一般形式如下：

ADT 抽象数据类型名称 {

数据对象：

……

数据关系：

……

操作集合：

操作名1：

……

……

操作名n：

}ADT抽象数据类型名称

总结：

抽象数据类型定义（ADT）

作用：抽象数据类型可以使我们更容易描述现实世界。例：用线性表描述学生成绩表，用树或图描述遗传关系。

定义：一个数学模型以及定义在该模型上的一组操作。

关键：使用它的人可以只关心它的逻辑特征，不需要了解它的存储方式。定义它的人同样不必要关心它如何存储。

例：线性表这样的抽象数据类型，其数学模型是：数据元素的集合，该集合内的元素有这样的关系：除第一个和最后一个外，每个元素有唯一的前趋和唯一的后继。可以有这样一些操作：插入一个元素、删除一个元素等。

时间复杂度的分类和理解

3.分类

按数量级递增排列，常见的时间复杂度有：

常数阶O(1), 注意：1仅仅表示常数的意思；

对数阶O(log2n),

线性阶O(n),

线性对数阶O(nlog2n),

平方阶O(n²)，

立方阶O(n³),...，

k次方阶O(n^k),

指数阶O(2ⁿ) 。

随着问题规模n的不断增大，上述时间复杂度不断增大，算法的执行效率越低。

4.关于对其的理解

《数据结构（C语言版）》------严蔚敏 吴伟民编著 第15页有句话"整个算法的执行时间与基本操作重复执行的次数成正比。"

基本操作重复执行的次数是问题规模n的某个函数f(n)，于是算法的时间量度可以记为：T(n) = O( f(n) )

如果按照这么推断，T(n)应该表示的是算法的时间量度，也就是算法执行的时间。

而该页对“语句频度”也有定义：指的是该语句重复执行的次数。

如果是基本操作所在语句重复执行的次数，那么就该是f(n)。

上边的n都表示的问题规模。

第1课 用C语言函数编写对话框之一直接实践

【参考资料：孙鑫VC++教学视频】

学习理论总是有点枯燥，而且也需要耐心，慢慢的去理解；那我们就直接实践，动手完成一个用C语言系统函数（API函数）实现的对话框；

一、实现步骤，总共5个步骤；

&#9733;&#9733;&#9733;&#9733;&#9733;创建一个完整的窗口需要经过下面四个操作步骤：

1）、设计一个窗口类（其实是一个结构体）；如：WNDCLASS wndcls;

     就是为这个结构体的各个分量赋值，设计一个窗口；

2）、注册窗口类； 如：RegisterClass(&wndcls);

3）、创建窗口； 如：CreateWindow(),CreateWindowEX();

4）、显示及更新窗口。如：ShowWindow(),UpdateWindow();

5）、消息循环GetMessage从消息队列中获得消息；

二、编程实现

1、建立空工程：win32 Application工程；

2、建立源文件：C++Source文件，不是头文件；

3、加头文件：windows.h, stdio.h;

4、定义主函数：WinMain函数，从msdn中拷贝函数头部；

具体做法：msdn索引中搜索WinMain，出现多个主题，选择Windows User Interface：Platform SDK；不要选择Windows CE API Reference;

拷贝并修改为：

int WINAPI WinMain(

  HINSTANCE hInstance,      // handle to current instance

  HINSTANCE hPrevInstance,  // handle to previous instance

  LPSTR lpCmdLine,          // command line

  int nCmdShow              // show state

)

{

      。。。。。。。。

}

5、主函数的参数暂且不表，后面有时间再补充；

现在我们准备实现主函数体：

     //第一步：设计窗口；WndClass，实际上是一个结构体；

       WNDCLASS wndcls;

       wndcls.cbClsExtra=0;

       wndcls.cbWndExtra=0;

       wndcls.hbrBackground=(HBRUSH)GetStockObject(BLACK_BRUSH);

       wndcls.hCursor=LoadCursor(NULL, IDC_CROSS);

       wndcls.hIcon=LoadIcon(NULL, IDI_ERROR);

       wndcls.hInstance=hInstance;

       wndcls.lpfnWndProc=WinSunProc;

       wndcls.lpszClassName="Weixin2003";

       wndcls.lpszMenuName=NULL;

       wndcls.style=CS_HREDRAW | CS_VREDRAW;

       //第二步：注册窗口；

       RegisterClass(&wndcls);

       //第三步：创建窗口；

       HWND hwnd;

       hwnd=CreateWindow("Weixin2003","北京维新科学技术培训中心",WS_OVERLAPPEDWINDOW,0,0,600,400,NULL,NULL,hInstance,NULL);

       //第四步：显示窗口

       ShowWindow(hwnd, SW_SHOWNORMAL);

       UpdateWindow(hwnd);

       //第五步：创建消息循环

       MSG msg;

       While(GetMessage(&msg, NULL, 0, 0))

       {

              TranslateMessage(&msg);

              DispatchMessage(&msg);

       }

6、主函数里面已经完成，接下来我们要创建窗口过程函数；

&#9733;用switch来处理各种消息；

switch(uMsg)

       {

       case WM_CHAR:

              char szChar[20];

              sprintf(szChar, "char is %d", wParam);

              MessageBox(hwnd, szChar,"weixin",0);

              break;

       case WM_LBUTTONDOWN:

              MessageBox(hwnd,"mouse clicked", "weixin", 0);

              HDC hdc;

              hdc=GetDC(hwnd);

              TextOut(hdc, 0, 50, "计算机编程语言培训", strlen("计算机编程语言培训"));

              ReleaseDC(hwnd, hdc);

              break;

       case WM_PAINT :

              HDC hDC;

              PAINTSTRUCT ps;

              hDC=BeginPaint(hwnd, &ps);

              TextOut(hDC, 0, 0, "维新培训", strlen("维新培训"));

              EndPaint(hwnd, &ps);

              break;

       case WM_CLOSE:

              if(IDYES==MessageBox(hwnd, "是否真的结束", "weixin", MB_YESNO))

              {

                     DestroyWindow(hwnd);

              }

              break;

       case WM_DESTROY:

              PostQuitMessage(0);

              break;

       default:

              return DefWindowProc(hwnd, uMsg, wParam,lParam );

       }

可以运行看效果，第一课最感性的直接实践就结束了，当然，对里面有些代码还会存在一些疑问，接下去会慢慢分析【待续】。