时空复杂度 C内存管理函数

1 时间复杂度&空间复杂度

如何分析算法的「时间复杂度」? - 知乎 (zhihu.com)

1.1 时间复杂度分析法则

1. 加法法则：只看复杂度最高的一项(即，O(n²+n) = O(n))。
2. 乘法法则：内外嵌套，则相乘。
3. 多参数，规模无法事先确定(比如参数m, n, 复杂度可能为O(m+n))。

   1.2 空间复杂度分析法则

   • 看申请空间的大小即可。

     2 C库函数

     2.1 malloc()

     声明

     分配一块大小为size字节的空间：

     void *malloc(size_t size)
     

     用法

     ```C char* str = (char *) malloc(15);

strcpy(str, “abc123”); printf(str);

#### 2.2 calloc() 
##### 声明
分配一块空间并**清零**，含有`nitems`个元素，每个元素大小为`size`：
```C
void *calloc(size_t nitems, size_t size)

用法

int *a = (int*)calloc(n, sizeof(int));

2.3 realloc()

声明

重新调整之前调用malloc或calloc所分配的ptr所指向的内存块的大小，调整为size字节：

void *realloc(void *ptr, size_t size)

• 如果为ptr空指针，则会分配一个新的内存块，且函数返回一个指向它的指针。
• 如果size为0，则释放ptr指向的内存块，返回NULL。

  用法

  str = (char *) malloc(15);
  /* 重新分配内存，增大到25字节 */
  str = (char *) realloc(str, 25);
  

  2.4 free()

  声明

  释放之前调用 calloc、malloc 或 realloc 所分配的内存空间：

  void free(void *ptr)
  

• 如果为ptr空指针，则不会执行任何动作。

  2.5 memset()

  memset()函数的用法详解-CSDN博客

  用法

  void *memset(void *str, int c, size_t n)
  

  表示将int型的值c赋给地址str开始的n个字符(字节)。

  // str == "This is string.h library function"
  memset(str,'$',7);
  // str == "$$$$$$$ string.h library function"
  

  如果str是int*类型，每个int变量占4字节。用sizeof(返回对象字节数)即可:

  memset(str, 0, sizeof(str));
  

  建议第3个参数写sizeof(str)，而非特定值(以免int*型4字节错误)：

  #define NUM_ARR 26
  int arr[NUM_ARR];
  memset(arr, 0, sizeof(arr)); //正确
  memset(arr, 0, NUM_ARR); //错误, 实际为NUM_ARR*4
  

  注意事项

  如果地址str是char类型，则c可以为任意字符；如果是int类型，则c只能为-1或0。 原因：memset是逐字节赋值的，但int类型是4字节，所以memset会给1个int变量中的每个字节赋值1次，总共赋重复的4个字节(比如，若c取100(二进制为01100100)，则int变量赋为01100100 01100100 01100100 01100100，转十进制int，实际为1684300900，不符合要求)。 而对于int型，-1对应0xFFFFFFFF，0对应0x00000000。截取8位并重复赋值，仍得到(FF FF FF FF)或(00 00 00 00)，转十进制int，仍为-1或0。所以不会有这样的问题。

  memset初始化为”无穷大”

  memset(a , 0x3f , sizeof a);
  

  巧妙之处在于，会将所有int变量赋为0x3F3F3F3F，是一个与$2^{31}-1$数量级相同的数。