C语言基础知识之三

xiaoxiao2021-02-27  385

时间复杂度与空间复杂度

1.时间复杂度 T(n)=O(f(n)) 只保留最高项、不要系数

(1){++x;s=0;} O(f(n))=O(1) (2)for 1层循环 O(f(n))=O(n) (3)for 2层循环,O(f(n))=O(n^2) (4)for 3层循环,O(f(n))=O(n^3) (5)

for(int i=2;i<=n;i++) for(int j=2;j<=i-1;j++) {++x;a[i,j]=x;}

共2*(0+0+1+2+…+n-2)次,即O(f(n))=O(n^2) (6)for(int i=1;i<=n;i*=2;) 共log(n)2;即O(f(n))=O(log(n)2) (7)for(int i=1;i<=sqrt(n);i++) O(f(n))=O(n^(1/2)) (8)递归中 return Fun(n/2)+n; 即O(f(n))=O(log(n)2) ,与第(6)类似

2.空间复杂度 实现算法所需要的额外的辅助空间

局部变量和全局变量

从变量的作用域,变量分为局部变量和全局变量 从变量的生存期,变量的存储方式分为静态存储方式和动态存储方式 1.局部变量的存储类别 局部变量:在函数内部定义的变量 主函数中定义的变量是局部变量,形参也是局部变量 作用域:只在本函数内部有效 (1)自动变量(auto变量) 不专门声明为static(静态)存储类型,都是动态的分配存储空间,它的默认值随机,数据存储在动态存储区中,函数调用结束时就自动释放这些存储空间。 (2)静态局部变量(static局部变量) 有关键字static,它的默认值为0,在静态存储区内分配存储单元,局部变量的值在函数用结束后继续保留原值,即其占用的存储单元不释放。 2.全局变量的存储类别 全局变量:在函数外定义,不安全 作用域:整个工程内都可以使用,从变量的定义处开始,到本程序文件的结尾 内存区域:静态变量区 生命周期:运行时被创建,退出时被销毁 默认值:0 (1)外部变量 关键字extern可以对该变量做“外部变量声明”,表示把该变量的作用域扩展到此位置,可以扩展到一个文件,也可以扩展到其他文件。有了此声明,就可以从“声明”处起,合法的使用该外部变量。如:extern int A,B,C; (2)静态外部变量(用static声明) 将外部变量的作用域限制在本文件中

用static声明一个变量的作用是:对全局变量用static声明,把它分配在静态存储区,该变量在整个程序执行期间不释放,其所分配的空间始终存在; 对全局变量用static声明,则该变量的作用域只限于本文件模块。

数组的数据类型

1.一维数组

int arr[10]={0,1,2,3,4,5,6,7,8,9,};

如内存为arr分配10个格子 arr 表示数组首元素地址,如数组arr首地址为0x00d2fef8, 类型为int * arr+1 表示格子号为1的元素的地址,如0x00d2fefc,与第0个格子地址差值为4,类型为int * arr[0] 表示格子号为0的元素的内容,此时为0, 类型为int arr[1] 表示格子号为1的元素的内容,此时为1, 类型为int arr[0]+1 表示格子号为1的元素的内容,即arr[1],此时为1, 类型为int

2,二维数组 int brr[3][4]={0,1,2,3,4,5,6,7,8,9,10,11}; 如分配3*4的内存空间 brr 表示第0行首地址为0x010ffb34 , 类型为int(*p)[4],即数组指针 brr+1 表示第1行首地址为0x010ffb44, 类型为int(*p)[4] brr[0] 表示第0行第0列元素地址为0x010ffb34, 类型为int * brr[0]+1 表示第0行第1列元素地址为0x010ffb38, 类型为int * brr[1] 表示第1 行首地址为0x010ffb44, 类型为 int* brr[0][0] 表示第0行第0列元素内容为0, 类型int brr[0][0]+1 表示第0行第1列元素内容为1, 类型int brr[1][0]+1 表示第1行第1列元素内容为5, 类型为int

转载请注明原文地址: https://www.6miu.com/read-2647.html

最新回复(0)