#1015. 寒域爷的奇怪代码

题目类型:答案提交 评测方式:Special Judge
上传者: skyair

题目描述

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

代码1

该函数出自两年前的ACM小学期课程中,用于实现求从1加到x的和

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

代码2

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

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

代码3

这一坨代码出自刚刚接触C语言的小透明寒域,该函数用于将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

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

std::priority_queue 支持以的时间复杂度插入任意元素,删除最小元素和的时间复杂度查询最小的元素。

#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

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

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

代码6

JM看到寒域的垃圾代码后劈头盖脸训斥了寒域一顿,并修改成了下面的函数。该函数用于求斐波那契数列的第x项()

#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 = 0, maxx = 0;
	bool sign[30];
	memset(sign, 0, sizeof(sign));
	for (i = 0, j = 0; j < s.length(); ++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;
}

输入格式

没有输入

输出格式

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

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

时间复杂度 你要写的内容
1
logn
n
nlogn
n2
n3
n4
2n
n!

样例

没有样例

数据范围与提示

Hint

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

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

编辑器加载中 …