数组与字符串长度的复杂度差异：为何sizeof是O(1)而strlen是O(n)？

这个问题问到点子上了！你观察到的sizeof（数组操作O(1)）和strlen（字符串操作O(n)）的差异，本质是C语言里数组与标准字符串的存储设计逻辑完全不同导致的，咱们拆开来聊：

先说说数组的sizeof为什么是O(1) #

不管是静态数组还是变长数组（VLA），sizeof都能在常数时间内拿到结果：

• 对于静态数组，比如char arr[20];，编译器在编译阶段就已经确定了数组的大小，sizeof(arr)直接返回编译时计算好的固定值，完全不需要运行时遍历。
• 就算是运行时才确定大小的变长数组，比如int n = 10; char arr[n];，编译器也会在数组创建时，把它的长度存在栈帧的某个固定位置，sizeof(arr)只需要直接读取这个预存的数值就行，全程没有遍历操作，自然是O(1)。

再看strlen为什么必须是O(n) #

C语言的标准字符串，本质是以空字符'\0'作为结束标记的字符数组，但它有个关键设计：没有额外存储字符串的实际长度信息。

举个例子，你定义char str[] = "hello";，内存里存的是h e l l o \0——这里面只有字符和结束标记，没有任何地方记录“这个字符串长度是5”。所以strlen要知道长度，只能从字符串的起始地址开始，逐个字符扫描，直到碰到'\0'才停止。每一个字符都要检查一遍，时间复杂度必然是O(n)，n就是字符串的实际长度。

额外补充：想O(1)查字符串长度怎么办？ #

如果想要常数时间获取字符串长度，你得自己给字符串加个“长度元数据”，比如定义一个自定义结构体：

typedef struct {
    char* content;
    size_t length;
} MyString;

这样你要查长度的时候，直接取my_str.length就行，完全不用遍历。但这就不是C标准库认可的字符串了，像strcpy、printf这类标准函数没法直接用它，得自己实现对应的操作逻辑。

内容的提问来源于stack exchange，提问作者allstar