题目描述

🏆WPM 最近突然精神抖擞，写下了大篇代码。刚刚学完时间复杂度的 wbt 试图在一晚上弄懂 🏆WPM 在代码中蕴含的深邃的思想，但是它却难以分析 🏆WPM 的代码。于是愤怒的 wbt 把你抓来了，要你为他讲解 🏆WPM 代码的时间复杂度，如果他听不懂的话就把你喂给 🏆WPM 制造更多的代码。

代码1

该函数出自一年前的国庆集训中，用于实现求从1加到x的和

int sum(int _Xx) {
	int ret = 0;
	for (int i = 1; i <= _Xx; i++) ret += i;
	return ret;
}

代码2

代码1被 🏆WPM 魔改后，大大降低了时间复杂度，仍然是用于实现求从1加到x的和

inline int sum(int _Xx) { return (1 + _Xx) * _Xx / 2; }

代码3

这一段代码出自刚刚接触C语言时的小透明 🏆WPM，该函数用于将 arr 数组中的 num 个元素排序

void bubble_sort(int* arr, int num) {
	for (int i = 0; i < num - 1; i++)
		for (int j = 0; j < num - i - 1; j++)
			if (arr[j] < arr[j + 1]) arr[j] ^= arr[j + 1] ^= arr[j] ^= arr[j + 1];
}

代码4

在 🏆WPM 偶然间翻看自己以前写的破烂代码的时候，他将代码3修改成了下面的样子。该函数用于将 arr 数组中的 num 个元素排序

#include <queue>
void heap_sort(int* arr, int num) {
	std::priority_queue<int> heap;
	for (int i = 0; i < num; i++) heap.push(arr[i]);
	for (int i = 0; i < num; i++) {
		arr[i] = heap.top(); 
		heap.pop();
	}
}

代码5

这个代码出自 🏆WPM 闲暇时候用来测试 Java 语言和 C 语言的速度差距。该函数用于求斐波那契数列的第x项

long long int fibonacci(int _Xx) {
    if (_Xx <= 2) return 1;
    return fibonacci(_Xx - 1) + fibonacci(_Xx - 2);
}

代码6

🏆WPM 看到 wbt 的垃圾代码后劈头盖脸训斥了 wbt 一顿，并修改成了下面的函数。该函数用于求斐波那契数列的第x项($x<1000$)

#include <cstring>
long long int fibonacci(int _Xx) {
	static long long int save[1000];
	static bool first = true;
	if (first) first = false, memset(save, -1, sizeof(save));
	if (save[_Xx] != -1) return save[_Xx];
	if (_Xx <= 2) return 1;
	return save[_Xx] = fibonacci(_Xx - 1) + fibonacci(_Xx - 2);
}

代码7

该函数用于计算最长的每个字母最多出现一次的子字符串的长度，出处已经不可考。

#include <string>
int lengthOfLongestSubstring(std::string s) {
	int i, j, len = s.length(), maxx = 0;
	bool sign[30];
	memset(sign, 0, sizeof(sign));
	for (i = 0, j = 0; j < len; ++j) {
		while (sign[s[j] - 'a'] == 1) {
			sign[s[i] - 'a'] = 0;
			++i;
		}
		sign[s[j] - 'a'] = 1;
		maxx = std::max(maxx, j - i + 1);
	}
	return maxx;
}

代码8

编不下去了qwq

int search(int start, int end, int key) {
    int ret = -1;
    int mid;
    while (start <= end) {
        mid = start + ((end - start) >> 1);
        if (arr[mid] < key) start = mid + 1;
        else if (arr[mid] > key) end = mid - 1;
        else {
            ret = mid;
            break;
        }
    }
    return ret
}

输入格式

没有输入

输出格式

这是一道提交答案题，你应该把你分析的结果按照下面的格式直接写在提交中。

如果满足多个时间复杂度，请选择最早出现的那一个。

时间复杂度	你要写的内容
$O(1)$	1
$O(\log n)$	logn
$O(n)$	n
$O(n \log n)$	nlogn
$O(n^2)$	n2
$O(n^3)$	n3
$O(n^4)$	n4
$O(2^n)$	2n
$O(n!)$	n!

样例

没有样例

数据范围与提示

Hint

注意本题的提交方式和通常的题目不同，仔细看，如你所见，在提交界面左侧有代码1.usr，代码2.usr，……，代码8.usr这8个小节，你需要在每一小节都填写答案，填写的内容与题目描述中的8份代码一一对应。

注意本题答案提交的答案不会被网页暂存在输入框中，多次提交需要多次输入8个小节，建议在本地写好然后往上复制，不然一旦WA了你就得全部重做了。