徐海学院の

徐海学院の

课堂引思的简单记录——徐海学院

目录

5. 给定程序时间复杂度的递推公式：T(1)=1，T(N)=2T(N/2)+N。则程序时间复杂度是（C）

6.选择题（C）

7.指针小知识普及

8.*p = NULL是啥？占空间？值多少？（C）

1.求下面程序段的时间复杂度

    x = 91;y = 100;while (y > 0)if (x > 100){x = x - 10; y--;}elsex++;

讲解：

程序执行时要么是y-- 要么是x++ 所以循环程序执行次数就是由x 和 y 决定 它是一个常数 所以是T(n)=O(1)

2.求下面程序段的时间复杂度

    i = 1;k = 0while (i < n){k = k + 10 * i; i++;}

讲解：

 i=1；循环中i++直到n 而实际上循环体被执行n-1次 所以是 T(n)=O(n-1)

3.求下面程序段的时间复杂度

int func(int n)
{int i = 0, sum = 0;while (sum < n)  sum += ++i;return i;
}

讲解：

设执行了k次，则 1 + 2 + 3 + … + k = n         k(k+1)/2=n        n1/​2

4.求下面程序段的时间复杂度

if ( A > B ) {for ( i=0; i<N; i++ )for ( j=N*N; j>i; j-- )A += B;
}
else {for ( i=0; i<N*2; i++ )for ( j=N*2; j>i; j-- )A += B;
}

讲解：

if ...先看哪个计算次数多，然后取最坏的。

很显然我们发现if执行次数多。因为你看if里面第一句for循环和else里面第一句for循环，数量级是一样的，当然我们也认为是时间复杂度是一样的；再看if里面第二个for循环，很明显N*N>N*2，所以if的时间复杂度更大，我们只要计算if中的复杂度即可。

我们看到，第二句子for循环中，j是随着i而变化的，当i=0时候，循环执行N^2-0次；i=1时，循环执行次数N^2-1次；......

(N^2-0) + (N^2-1) + (N^2-2) + … + (N^2-N+1) = N^3 – N(N-1)/2，所以时间复杂度是N^3

5. 给定程序时间复杂度的递推公式：T(1)=1，T(N)=2T(N/2)+N。则程序时间复杂度是（C）

A：O(logN)        

B：O(N​)      

C：O(NlogN)        

D：O(N2)

讲解：

T(N) = 2T(N/2)+N

        = 2(2T(N/4)+N/2)+N

        = 4T(N/4)+2N

        = 4(2T(N/8)+N/4)+2N

        = 8T(N/8)+3N

        =.......................

假定迭代了k次，使得N/2^k=1            T(N) = 2^k * T(1) + kN        将T(1)=1、k=log2N代入

得T(N) = N + NlogN

6.选择题（C）

问：b各是什么？

int *p, b;
int* p, b;

小知识：

其实上面两种写法是一样的。指针可以int* p    也可以int  *p。但是老师说标准是int   *p，这和我的记忆有点偏差。。。

A：指针、指针

B：指针、普通变量

C：普通变量、普通变量

D：普通变量、指针

讲解：

int  *p，b;可能你觉得b会是普通变量？   int*  p，b;你觉得b不是普通变量？？错❌❌❌❌❌❌❌❌❌❌❌❌❌❌❌❌❌❌❌❌❌❌

两处的b都是一个普通变量。

指针不会因为*号的远近来判断，每个指针前面都得有属于自己的*号！！，不是int*  都概括了的！！

7.指针小知识普及

注意：

算数运算

1. 存在：    指针 - 指针   、指针+   、  指针-    、指针自增自减    、       
2. 不存在！！！————>    指针加指针！！！，        不要与    指针+   混淆

下标运算：[   ]

关系运算：p>q    、 p<q   、  p==q

赋值运算：p=q

8.*p = NULL是啥？占空间？值多少？（C）

int* p = NULL;

注释：（NULL等会出一篇博客细讲！！）

A：p不占存储空间，

B：p占存储空间，里面的值是空

C：p占存储空间，里面的值一定是0

讲解：

p是变量，是变量就会占存储空间！！

NULL值是0。