h****n
发帖数: 1093 | 1 恩。不过我觉得复杂度应该是O（N×avg（M）） |
|
p*****2
发帖数: 21240 | 2
应该是nlogn
每插入一个是logn的复杂度，一共有n个。 |
|
n*****g
发帖数: 178 | 3 请教大家，下面是我自己写的一个移除已排列好的数组中的重复袁福的代码，但我对时
间复杂度的概念比较模糊，能否指教一下？？
需不需要按最坏和平均情况来分析，我一直搞不懂..
int removeDuplicateSortedArray(int A[], int n)//leetcode all passed
{
int duplicate=0,prev=0,cur=prev+1,len,newPosit;
if(n==1)//一个元素就不考虑了
return 1;
if(n==0) //一个元素都没有更不考虑
return 0;
for(prev=0;prev
{
cur = prev+1;
if(A[prev]==A[cur])//找到相同元素
{
//直接把相同元素后面的全幅往前移一格
... 阅读全帖 |
|
n****r
发帖数: 120 | 4 你这个是O(N^3)的时间复杂度！删除重复元素，若是已排序数组，应该做到O(n)，未排
序数组，应该是O(N^2).
前两个if完全可以合成一个if，其实可以完全不需要这个if。
在处理元素a[i]时，从i+1开始查找相同的元素，找到后就把后面的所有元素前移。这
个地方不科学！比方{1,1,1,1,1},既然是已排序数组，为什么不一直跳过重复元素呢？ |
|
w****x
发帖数: 2483 | 5
可能指的是amortized的复杂度是O(n^2)，毕竟当前的max size很大的限制了计算量，
感觉有可能是O(n^2),但是数学功底有限，不知道怎么证明 |
|
w****x
发帖数: 2483 | 6
算法导论上有，比如说斐波那契数列递归的时间复杂度？ |
|
|
c*******r
发帖数: 309 | 8 For example, given candidate set 2,3,6,7 and target 7,
A solution set is:
[7]
[2, 2, 3]
这题如果用backtrack来做的话复杂度是多少？ 感觉是O(N^2) |
|
|
c********t
发帖数: 5706 | 10 请问这个is balanced tree的程序(cc 4.1答案1），空间复杂度为什么是O(n^2)？怎么
算出来的啊？
public int getHeight(TreeNode root){
if(root==null) return 0;
return Math.max(getHeight(root.left), getHeight(root.right)+1;
}
public boolean isBalanced(TreeNode root) {
if(root==null) return true;
int heightDiff=getHeight(root.left)-getHeight(root.right);
if(Math.abs(heightDiff) > 1) return false;
else return isBalanced(root.left) && isBalanced(root.right);
} |
|
c***s
发帖数: 192 | 11 space是O(logn)吧(average). worst case 是O(n)?
时间复杂度估算就可以了啊，判断第一层是 n, 第二层是 2 * （n/2), 第三层是4*(n/
4) .... |
|
c********t
发帖数: 5706 | 12 你这样算的时间复杂度不是 O(nlogn)吗？我其实也认为时间是O(nlgn)。但答案说是O(
n^2).
空间不会算，肯定大于O(lgn),为什么你说worst case是O(n)?
n/ |
|
c***s
发帖数: 192 | 13 严格来说这道题的复杂度是 O(1).
只要大于12位的都扔掉，小于等于12位的肯定能在一个常数时间内完成。
possible |
|
p*****p
发帖数: 379 | 14 new完没有delete
复杂度不对
用heap就行了，其他纯属吃力不讨好 |
|
|
j******s
发帖数: 48 | 16 9.10 n boxs, height,width,depth, find the max height.
Solution,
Sub-problem, find the max depth that is using box b_i as bottom. Using
recursion + cache.
请问各位大神算法的复杂度是多少，怎么得出来的？谢谢！ |
|
f**********t
发帖数: 1001 | 17 我有一个M*N维的矩阵
希望找到一个m*n维的子矩阵使得其元素和最大
这个子矩阵的行和列不一定要连续
这个问题有好的解么？
就比如说，一个矩阵是3*3的
设每行每列的编号是(1, 1,) (1, 2), (1, 3)(2, 1,) (2, 2), (2, 3)(3, 1,) (3, 2)
, (3, 3)，则(1, 1)(1, 3)(3, 1)(3, 3)这四个点组成的也算是个子矩阵
目前有想法，但时间复杂度很大。感觉好像只有枚举法来做这个问题。不知大家有没有
更好的解法。 |
|
i******r
发帖数: 793 | 18 经典算法题
可以枚举左上和右下两个顶点，复杂度O(n^4)
模仿最大子段和的O(n)算法，可以优化到O(n^3)
请自行google ‘最大子矩阵’ |
|
y****n
发帖数: 743 | 19 我的想法是:
1. 建立矩阵1，纵向用slide window对原矩阵求和。
2. 建立矩阵2，横向用slide window对矩阵1求和。
3. 扫描矩阵2，找到最大值就是目标矩阵所在位置
复杂度O(M*N)，不知道有没有遗漏什么 |
|
x*********w
发帖数: 533 | 20
很多就是画recursion tree硬看？比如merge sort?
heapify等可以写个数列，发现一只是收敛的那就是n了？
有些比如用队列实现max number in moving window的算O(n)就是每个元素只如队列出
队列一次？
有些用到组合的，比如permutation, combination啥的？
计算平均时间复杂度用到些概率，期望啥的... 不过这个有点难。。。 |
|
r**u
发帖数: 1567 | 21 Given a string s, partition s such that every substring of the partition is
a palindrome.
Return all possible palindrome partitioning of s.
For example, given s = "aab",
Return
[
["aa","b"],
["a","a","b"]
]
DFS就是要枚举所有可能的划分，然后检查是否是palindrome吧，中间如果发现划分不
满足palindrome了，就backtrack。这个复杂度应该怎么求？ |
|
|
c***w
发帖数: 134 | 23 题目是打印n个质数。
请问最简单的这种方法，时间复杂度是多少？谢谢
每一次计算到一个n的数，都要和n个做n个判断所以是n^n吗
/**
* naive way.
* I think it takes O(n^n) time?
*/
public static void prime(int n) {
boolean[] primes = new boolean[n + 1];
for (int i = 2; i < primes.length; i++) {
if (isPrime(i)) {
primes[i] = true;
}
}
print(primes);
}
public static boolean isPrime(int num) {
for (int j = num - 1; j > 1; j--) {
if (num % j ... 阅读全帖 |
|
|
z****e
发帖数: 54598 | 25 先取一个n高的高度
然后把n顶端的那个1往右边走
比如5
4+1
3+2
3+1+1
2+2+1
2+1+1+1
1+1+1+1+1
总共有n行，每一行都不超过n个数，你要做的就是筛选掉不合格的组合
而所谓不合格的就是当前高度大于左边的高度的情况，比如
2+2+1之后的
2+1+2，最后一个2大于左边的1，干掉
如果合格的组合，就放到result list里面去
所以最后复杂度是n^2
递推公式别管了，用欧拉命名的公式和定理，可想而知了 |
|
r*********n
发帖数: 4553 | 26 明显不是n行啊？ 你这个例子已经是6行了啊。
如果是6
5 1
4 2
4 1 1
3 2 1
3 1 1 1
2 2 1 1
2 1 1 1 1
1 1 1 1 1 1
已经8行了
数字越大，越来越多的行会已相同的数字开头，所以行数会远远大于n。wiki上面p(100
) =190,569,292，如果真的有O(n^2)算法存在，p(100)最多是10000，因为你最多只能
做10000次比较。
按照wiki上面的recursion formula
p(1, n) = 1 + sum_{k=1}^{n/2}p(k, n-k)
这个复杂度是O(2^{n/2})
PS：这个题要不是见过，基本没有可能现场推出来wiki的公式。下次大家面烙印的时候
不用手软了，直接上来第一题就让他证明yitang的7千万。 |
|
|
i******t
发帖数: 22541 | 28 f(n) = f(n-1)+f(n-2)
所以总共树的高度是 n , 每i层的节点数 2^i
所以总共节点数 2^0 + 2^1 +... +2^n >2^n
所以
错略复杂度是 THETA(2^n)
？
所以是 np-hard 问题？ |
|
a*****u
发帖数: 1712 | 29 复杂度是O(n)
念order of，不是theta
Np-hard好像也不是你说的那样定义的
★ 发自iPhone App: ChineseWeb 7.8 |
|
i******t
发帖数: 22541 | 30 我说错了
我应该说的是 这种用原始递归做的时候的复杂度 是 大约 2^n
用 DP 是可以o(n)的
还有个方法是 logn
easy |
|
h**o
发帖数: 548 | 31 recursive法:
T(n)高2n, 每层： 2^0,2^1..., 2^(2n), 所以 time是:O（4^n)吗?
空间复杂度怎么求？ |
|
a**********0
发帖数: 422 | 32 如果扩展到找三个数whose sum 已知 时间复杂度可以做到多少？ |
|
A*********c
发帖数: 430 | 33 Calatan Number。复杂度 4^n/(lower order) |
|
t*********2
发帖数: 55 | 34 请问， 关于patter matching 复杂度：
如果， pattern size is M, string length is N,
the worst complexity of the best algorithm is: O(M+N)
对不对， 多谢！ |
|
c***5
发帖数: 158 | 35 老觉得算法的复杂度分析很难，有好书和方法推荐吗？谢谢。 |
|
b*******g
发帖数: 57 | 36 请问如何评估下面代码的时间复杂度？谢谢。
double sqrt(double x) {
double y = x/2;
double sq = y*y;
double epsilon = DBL_EPSILON;
while (abs(x-sq) > epsilon) {
y = (y+x/y)/2;
sq = y*y;
}
return y;
} |
|
d**k
发帖数: 797 | 37 之前我计算时间复杂度都只是考虑到算法本需要的时间
比如说我在实现中用一个ArrayList来存东西，我就默认ArrayList的存取都为恒定值
然后昨天被面试官质疑了
说我用ArrayList的insertion是O(n)的操作，所以实际的time complexity比我估计的
大很多
我想问一下这种情况多见么？
那我岂不是还要熟悉某个特定语言中数据结构的怎么实现的？ |
|
z****e
发帖数: 54598 | 38 arraylist复杂度是o(n)那是最糟糕的情况
这个考官也是不懂
arraylist的insert明明是o(1) amortized
因为list本身有长度，如果超过了，需要扩充内存
但是平均起来是个常量
这个题目也不少太少见，见过几次 |
|
|
z****e
发帖数: 54598 | 40 那你说，楼主妹子说arraylist的复杂度说错了吗？ |
|
d**k
发帖数: 797 | 41 那我们一般分析时间效率要不要考虑overhead效率？
还是就算复杂度效率就可以了？ |
|
a********m
发帖数: 15480 | 42 overhead只是常数，慢点总是有限，区别是3秒还是4秒这种。算法复杂度是数量级问题
，区别是3秒还是3年的问题。big o里面常数都可以忽略。overhead一般在这部分。 |
|
z****e
发帖数: 54598 | 43 arraylist这个类根本没有append和insert方法，只有一个add
java的list接口就只定义了add，没定义其他方法
看下面
我问楼主后的答覆
发信人: duck (五月飞花), 信区: JobHunting
标 题: Re: 问一个时间复杂度的问题，求教求教
发信站: BBS 未名空间站 (Sat May 31 11:44:06 2014, 美东)
我就是用了add 而已
他问我ArrayList的add是什么时间的
我张口就,常数阿
他表示很质疑 |
|
t**r
发帖数: 3428 | 44 走迷宫的 时间复杂度是多少？谢谢 如这个解法
#include
// Maze size
#define N 4
bool solveMazeUtil(int maze[N][N], int x, int y, int sol[N][N]);
/* A utility function to print solution matrix sol[N][N] */
void printSolution(int sol[N][N])
{
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
printf(" %d ", sol[i][j]);
printf("n");
}
}
/* A utility function to check if x,y is valid index for N*N maze */
bool isSafe(int maze[N][N], int x, int y)
{
// if (x,y out... 阅读全帖 |
|
g***j
发帖数: 1275 | 45 为啥这个可以过？ 下面这个时间复杂度是 O^3 吧？
class Solution {
public:
vector > fourSum(vector &num, int target) {
// Note: The Solution object is instantiated only once and is reused
by each test case.
vector tmp;
vector> results;
if(num.empty()) return results;
sort(num.begin(), num.end());
for(int i=0; i
{
for(int j=i+1; j
{
int temp ... 阅读全帖 |
|
m******3
发帖数: 346 | 46 应该不是N^3,最里面一层是binary search, 应该复杂度是N^2LogN
reused |
|
f*****u
发帖数: 308 | 47 好吧，我只是问一下这道题的这种recursion基本解法的算法复杂度的分析问题撒。当
然知道这题有dp的优化解法。不过还是感谢提醒吧。 |
|
a***e
发帖数: 413 | 48 多谢大牛，我觉得它们都是O（N^2），但看2说自己是O（N）又不确定了。
下面这种解法应该怎么分析复杂度呢？我觉得是O（N）但还是不确定。
class Solution {
public:
TreeNode *buildTree(vector &pre, vector &in) {
int i=0,j=0;
TreeNode *root=new TreeNode(0x80000000);
TreeNode *pp=NULL,*ptr=root;
stack sn;sn.push(root);
while (j
if (sn.top()->val==in[j]) {
pp=sn.top();
sn.pop();
j++;
} else if (pp) {
ptr... 阅读全帖 |
|
a***e
发帖数: 413 | 49 Given n, generate all structurally unique BST's (binary search trees) that
store values 1...n.
For example,
Given n = 3, your program should return all 5 unique BST's shown below.
1 3 3 2 1
/ / /
3 2 1 1 3 2
/ /
2 1 2 3
这种题如果没见过我很难想出来，看了答案也不知道复杂度怎么算。汗， 现在在国内
还惦记着这些题。
class Solution {
public:
vector generateTrees(int n) {
if (n==0) retur... 阅读全帖 |
|
|
