求时间复杂度哦o(n）变为o(1)算法，程序？求大侠解惑！

1. 求时间复杂度哦o(n）变为o(1)算法，程序？求大侠解惑！

O(n)： 一般是只做一次遍历
O(1) ： 直接定位数据

比如：在一个数据中查找一个数这个复杂度就是O(n)的
如果转成MAP存储就变成O(1)了

2. C：RMQ算法（求任意子区间内的最大值）（已通过

这个方法巨复杂……貌似是先把RMQ通过笛卡尔树变成LCA，然后通过欧拉序列把LCA变成±RMQ，然后再通过一个什么分块的table在O(n)-O(1)时间内解决。

3. 求教时间复杂度的计算： O(1)+O(2)+...+O(N-1)+O(N)=? O(1)+...+O(N/4)+O(N/2)+O(N)=?

算法复杂度，其实很好算的:)
 
首先因为它这里的N代表无穷大，
所以这里要用N的最大项去计算
 
然后别的数值相对于N来说，常数是忽略不计的
 
另外相关的可以进行归纳函数的，要写成对应的函数
你这里就是一个等差求和公式，和一个等比求和公式，
但是为什么最后是O(1)?
 
然后写成函数后，就保留最大项，同时保留最大项的常数
然后再求个导就出来了……

4. 如何对n个整数数进行排序，要求时间复杂度O(n)，空间复杂度O(1)

题目：如何对n个不重复出现的整数序列进行排序，已知这些数的范围为(0-65535)，要求时间复杂度O(n)，空间复杂度O(1)分析：可以申请一个大小为65536的数组A，数组的x下标代表数字x，A[x]代表x 在整数序列中出现的次数。扫描一遍整数序列就可以完成对该整数序列的排序,时间复杂度为O(n)应为已知范围，申请大小为65536的数组，大小为常量，所以空间复杂度为O(1)代码：�0�2 1: #include 2: #define SIZE 65536 3: void rangeSort(int *array,int len) 4: { 5: int data[SIZE] ; 6: int i = 0 ; 7: int j = 0 ; 8: memset(data,0,SIZE*sizeof(int)) ; 9: for(i=0;i<len;++i){ 10: data[array[i]] ++ ; 11: } 12: i = 0 ; 13: for(j=0;j<SIZE;++j){ 14: if (!data[j]){ 15: array[++i] = j ; 16: } 17: } 18: }

5. 如何实现删除一个字符串中重复的字符,时间复杂度为O(n),空间复杂度为O(1)

精减重复字符

<!--

function sortNumber(a,b)
	{
	return a-b;
	}

function sbf(){
	var s = ascii.value;
	var strLen = s.length;
	var newStr = "";
	var newArr = [];
	for(i=0;i<strLen;i++){
		newStr += "&#"+s.charCodeAt(i)+";";
		}

	newStr.replace(/([^;&#][\d]*)/g, function($0, $1, i){
        if(newStr.indexOf($1) == i) newArr[newArr.length] =  $1;
    		});
	newArr.sort(sortNumber);

	newStr = "";
	for(i=0;i<newArr.length;i++){
		newStr += "&#"+newArr[i]+";";
		}
	unicode.value = newStr;
	
	newStr = "";
	for(i=0;i<newArr.length;i++){
		newStr += ''+String.fromCharCode(newArr[i])+''+String.fromCharCode(32);
		}

	display.innerHTML=newStr + '不重复的字符数总计：'+newArr.length+' 个';
	return newArr;
	}
	
function fbo(){
	display.innerHTML=unicode.value;
	}
//-->





在此输入要精减排序的字符串


经过精减排序后的字符串的Unicode编码

6. 算法复杂度中的O(n)、O(nlgn)、O(n^2)等是什么意思

关于算法的复杂度计算，初学者一开始便容易进入完全定量的思考之中，这是难以到达的。算法复杂度在很多时候是对算法运行的时间一个大概的定性（或者说大数）描述，因为很多时候无法精确地描述一条代码究竟执行了多少时间。而任何一个算法运行的大多时间都集中在某一主体循环之中，像for,while之类，主体循环的次数往往跟某个或多个输入参数或环境变量有关。像O(n)、O(nlgn)、O(n^2)之类描述都是围绕主体循环次数和输入参数或者环境变量的关系展开的。
下面举一个例子，从给定的整型数组中查找与某一数相等的数的位置，显然对于没有排序的数组而言，需要从数组头部开始向后遍历比较，那么这个主体遍历循环就跟数组的长度有关，即算法复杂度为O(n)。

7. 为啥冒泡排序的最优时间复杂度是O（n）不是O（1）啊？

就是O(n)，维基百科是对的~
初始时数组中的数就已经排列完成了的话，还需要扫一遍数组的，所以是O(n)~
不懂可问，满意望采纳谢谢！

8. 算法分析中O（n）什么含义

O(n)这个大O表示的是最坏情况下的时间复杂度，就比如你举的例子，一共n^3次乘法和n^3次加法，那么加起来就是2×n^3。 然后如果有一个表达式f(n)，使得n趋于无穷大的时候，lim(2×n^3)/f(n)=常数c，那么就可以用大O表示。表示为O(f(n))，而且规定f(n)的表达式是不带常数的系数的，那么在这里f(n)=n^3。 一般用大O表示算法复杂度只需要取次数最高的项，而且去掉系数就OK了，不用每次都这么算的。三重循环而且每重循环都执行n次的话直接O(n^3)就好了。