面试题：C语言一维数组指针优化之复杂场景

Question

假设你有一个包含大量结构体的一维数组struct { int id; float value; } largeArr[10000]; 要求通过数组指针高效地找到value值最大的结构体元素，并给出优化思路及代码实现，说明优化前后在时间复杂度和空间复杂度上的变化。

Answer 1

未优化实现

#include <stdio.h>

// 定义结构体
typedef struct {
    int id;
    float value;
} Element;

// 未优化函数
Element* findMaxValueUnoptimized(Element largeArr[], int size) {
    Element* maxElement = &largeArr[0];
    for (int i = 1; i < size; i++) {
        if (largeArr[i].value > maxElement->value) {
            maxElement = &largeArr[i];
        }
    }
    return maxElement;
}

优化实现

// 优化函数
Element* findMaxValueOptimized(Element *largeArr, int size) {
    Element* maxElement = largeArr;
    Element *end = largeArr + size;
    while (largeArr < end) {
        if (largeArr->value > maxElement->value) {
            maxElement = largeArr;
        }
        largeArr++;
    }
    return maxElement;
}

优化思路

• 未优化：使用普通数组下标访问方式遍历数组，每次通过largeArr[i]访问元素。
• 优化：使用指针方式遍历数组，通过指针的算术运算largeArr++来移动指针，减少了数组下标计算的开销。在现代CPU架构下，指针运算通常更高效，因为它直接操作内存地址，减少了地址计算的复杂性。

时间复杂度

• 未优化：时间复杂度为 $O(n)$，因为需要遍历数组中的每一个元素，其中 $n$ 是数组的大小。
• 优化：时间复杂度同样为 $O(n)$，虽然使用指针方式遍历可能在实际运行中更快，但从渐进时间复杂度角度，依然是线性时间复杂度。

空间复杂度

• 未优化：空间复杂度为 $O(1)$，除了输入数组外，只使用了常数级别的额外空间，如maxElement和循环变量i。
• 优化：空间复杂度也为 $O(1)$，同样除了输入数组外，只使用了常数级别的额外空间，如maxElement、end和指针变量largeArr。

完整测试代码

#include <stdio.h>

// 定义结构体
typedef struct {
    int id;
    float value;
} Element;

// 未优化函数
Element* findMaxValueUnoptimized(Element largeArr[], int size) {
    Element* maxElement = &largeArr[0];
    for (int i = 1; i < size; i++) {
        if (largeArr[i].value > maxElement->value) {
            maxElement = &largeArr[i];
        }
    }
    return maxElement;
}

// 优化函数
Element* findMaxValueOptimized(Element *largeArr, int size) {
    Element* maxElement = largeArr;
    Element *end = largeArr + size;
    while (largeArr < end) {
        if (largeArr->value > maxElement->value) {
            maxElement = largeArr;
        }
        largeArr++;
    }
    return maxElement;
}

int main() {
    Element largeArr[10000];
    // 初始化数组
    for (int i = 0; i < 10000; i++) {
        largeArr[i].id = i;
        largeArr[i].value = (float)i * 1.5;
    }

    Element *maxUnoptimized = findMaxValueUnoptimized(largeArr, 10000);
    Element *maxOptimized = findMaxValueOptimized(largeArr, 10000);

    printf("未优化找到的最大value的id: %d, value: %f\n", maxUnoptimized->id, maxUnoptimized->value);
    printf("优化后找到的最大value的id: %d, value: %f\n", maxOptimized->id, maxOptimized->value);

    return 0;
}