bool linearSearch(int array[], int target) {
for (int i = 0; i < sizeof(array) / sizeof(array[0]); i++) {
if (array[i] == target) return true;
}
return false;
}

🎈求数组或列表的元素之和或平均值

int sum(int array[]) {
int result = 0;
for (int i = 0; i < sizeof(array) / sizeof(array[0]); i++) {
result += array[i];
}
return result;
}

double average(int array[]) {
return sum(array) / (double)(sizeof(array) / sizeof(array[0]));
}

✨对数时间复杂度O(log n)

对数时间复杂度 O(log n) 的算法指的是随着输入规模n的增长，该算法执行时间呈现出对数增长趋势。例如，当输入规模n增加1倍时，算法的运行时间可能会增加约2倍。常见的O(log n)算法通常是使用二分查找或者树结构等数据结构实现的。

🎈二分查找

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

以上代码中，二分查找算法每次将元素范围缩小一半，时间复杂度为 O(log n)

🎈堆排序算法

void heapify(int array[], int size, int i) {
int largest = i;
int left = 2 * i + 1;
int right = 2 * i + 2;
if (left < size && array[left] > array[largest]) largest = left;
if (right < size && array[right] > array[largest]) largest = right;
if (largest != i) {
swap(array[i], array[largest]);
heapify(array, size, largest);
}
}

void heapSort(int array[], int size) {
for (int i = size / 2 – 1; i >= 0; i–) {
heapify(array, size, i);
}
for (int i = size – 1; i > 0; i–) {
swap(array[0], array[i]);
heapify(array, i, 0);
}
}

以上代码中，堆排序算法使用了二叉堆的数据结构，每次都将元素拆分为两个相等长度的子集，并递归处理其中一个子集。因此，堆排序的时间复杂度为 O(log n)。在实现时，我们使用heapify()函数维护二叉堆的性质，用两个for循环来进行堆排序。

✨平方时间复杂度O(n^2)

平方时间复杂度 O(n^2) 的算法指的是随着输入规模n的增长，该算法执行时间呈现出平方增长趋势。例如，当输入规模n增加1倍时，算法的运行时间会增加约4倍

🎈冒泡排序

双重for循环

void bubbleSort(int array[], int size) {
for (int i = 0; i < size – 1; i++) {
for (int j = 0; j < size – i – 1; j++) {
if (array[j] > array[j + 1]) swap(array[j], array[j + 1]);
}
}
}

以上代码中，冒泡排序算法使用每一次内层循环来比较相邻元素的大小，并根据需要交换它们的位置，时间复杂度为 O(n^2)。在实现时，我们使用两个for循环分别遍历整个数组并比较相邻的元素。

🎈插入排序算法

void insertSort(int array[], int size) {
for (int i = 1; i < size; i++) {
int key = array[i];
int j = i – 1;
while (j >= 0 && array[j] > key) {
array[j + 1] = array[j];
j–;
}
array[j + 1] = key;
}
}

✨立方时间复杂度

三重循环

在这个例子中，我们使用了三重循环来演示立方阶时间复杂度的算法，其中第一重循环运行了 n 次，第二重循环也运行了 n 次，第三重循环也运行了 n 次，因此总的计算次数为 n * n * n，也就是立方阶时间复杂度 O(n^3)。

#include <iostream>

using namespace std;

int main() {
int n; // 输入规模
cin >> n;

for (int i = 0; i < n; i++) { // 第一重循环
for (int j = 0; j < n; j++) { // 第二重循环
for (int k = 0; k < n; k++) { // 第三重循环
cout << i * j * k << ” “; // 立方阶计算
}
}
}

return 0;
}

在实际编程中，由于立方阶算法的效率非常低下，通常应该尽可能避免使用它，或者通过一些技巧将其转化为更高效的算法，以提高程序的性能。

✨指数时间复杂度 O(2^n)

指数时间复杂度是指算法执行的时间与数据规模 n 的指数成正比，通常表示为 O(2^n)。一种计算方式是，在算法中使用了嵌套循环或递归，每次运算次数都是上一次的两倍或更多，这种情况就容易出现指数级别的时间复杂度。

🎈斐波那契数列

#include <iostream>
using namespace std;

int fib(int n) {
if (n <= 1) {
return n;
} else {
return fib(n – 1) + fib(n – 2);
}
}

int main() {
int n = 10;
for (int i = 0; i < n; i++) {
int res = fib(i);
cout << res << ” “;
}
cout << endl;
return 0;
}