C语言中的时间复杂度与空间复杂度

在C语言中，时间复杂度和空间复杂度是衡量算法性能的两个重要指标。它们描述了算法在处理输入数据时需要的时间和空间资源的增长趋势。
时间复杂度：
时间复杂度是衡量算法执行时间随输入规模增加而增长的度量。它表示了算法的运行时间与输入规模之间的关系。常见的时间复杂度包括：

1.常数时间复杂度（O(1)）：算法的执行时间与输入规模无关，即执行时间恒定。

void printFirstElement(int arr[]) {
    printf("%d\n", arr[0]);
}

在上述示例中，printFirstElement() 函数只打印数组中的第一个元素，无论数组的大小是多少，所需的时间都是恒定的。

2.线性时间复杂度（O(n)）：算法的执行时间与输入规模呈线性增长的关系。

int sumArray(int arr[], int n) {
    int sum = 0;
    for (int i = 0; i < n; ++i) {
        sum += arr[i];
    }
    return sum;
}

上述代码中的 sumArray() 函数计算数组中所有元素的总和。随着数组的大小增加，循环的迭代次数也随之增加，因此时间复杂度为 O(n)。

3.对数时间复杂度（O(log n)）：算法的执行时间随输入规模的增加而增长，但增长速度相对较慢。

int binarySearch(int arr[], int left, int right, int target) {
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] == target) {
            return mid;
        }
        if (arr[mid] < target) {
            left = mid + 1;
        }
        else {
            right = mid - 1;
        }
    }
    return -1;
}

上述代码演示了二分查找算法，在一个有序数组中查找目标元素。每次迭代，算法将搜索范围缩小一半，因此时间复杂度为 O(log n)。
空间复杂度：
空间复杂度是衡量算法在执行过程中所需的额外空间随输入规模增长而增加的度量。

4.常数空间复杂度（O(1)）：算法所需的额外空间是固定的，与输入规模无关。

int addNumbers(int a, int b) {
    int sum = a + b;
    return sum;
}

在上述示例中，addNumbers() 函数只需要几个整型变量来存储输入参数和结果，因此空间复杂度是常数级别的。

5.线性空间复杂度（O(n)）：算法所需的额外空间随着输入规模的增加而线性增长。

int* createArray(int n) {
    int* arr = (int*)malloc(n * sizeof(int));
    return arr;
}

上述代码中的 createArray() 函数动态分配了一个整型数组，并返回指向该数组的指针。数组的大小与输入规模 n 相关，因此空间复杂度为 O(n)。
请注意，这些只是一些示例，实际的算法可能具有不同的复杂度类别。通过分析时间复杂度和空间复杂度，可以评估算法的效率和资源需求，从而做出更好的算法设计和选择。