z****e
发帖数: 54598 | 1 dp应该是n^3的复杂度
每一次都从之前的答案中挨个拿出来
对每一个的每一位挨个加1看结果，这一步复杂度是n^2
然后放入set中，然后再在set里面去掉重复的数据，复杂度是n
n
所以最后复杂度是n^3
n^3强过递归的2^n的复杂度
也就是说楼主说的是对的咯？ |
|
f*********g
发帖数: 110 | 2 leetcode 上Unique Paths, 我写了一个递归，但不是很明白这个递归的时间复杂度和
空间复杂度。我觉得空间复杂度是O(m*n),时间复杂度是O(m*n).不知道对不对，请大家
指点。
public int uniquePaths(int m, int n) {
if(m==1|| n==1) return 1;
return uniquePaths(m-1,n)+uniquePaths(m,n-1);
} |
|
s*****a
发帖数: 310 | 3 在研究中需要分析一个算法的复杂度，其中要多次用到两个vector相加和相减。
用C的for循环的话，那复杂度是O(n). 但用GPU之类的并行运算方法，是不是也可以实
现复杂度O(1)?
同样，用Matlab来运算，似乎两个vector可以点对点一步实现相加减，似乎复杂度也是
O(1).
如果写论文分析算法复杂度的话，我到底是该用Q(1)还是Q(0).
似乎问题太简单，但是真的有点搞不清楚。希望大家能指点一下，非常感谢！ |
|
k***g
发帖数: 166 | 4 今天昂赛碰到这题，俺用dfs解的，还借了trie树来帮忙剪枝，大概是这样的：
wordSearch() {
for x
for y
dfs(x, y, res)
return res;
}
dfs(x, y, ..) {
if x,y invalid or not a prefix in trie, return
word += b[x][y]
res <- word
visited[x][y] = true
dfs(x-1, y ..)
dfs(x+1, y ..)
dfs(x, y-1 ..)
dfs(x, y+1 ..)
visited[x][y] = false
}
面试官问复杂度，我刚说到wordSearch()里面那个循环里的每一次dfs是O(M*N)，这时
候面试官就说：不对，你在那个dfs里面还有四个dfs，每个都要走O(M*N)的，最后搞下
来，你的这个解法复杂度是O((M*N)!)
我说：那个，图dfs的复杂度应该是O(E+V)，在这里不就是O(M*N)么。于是面试官就给
我在白板上画，说你这个一下哗哗... 阅读全帖 |
|
n******7
发帖数: 12463 | 5 【 以下文字转载自 Programming 讨论区 】
发信人: nowhere7 (折腾), 信区: Programming
标 题: 并行可以降低计算复杂度？？
发信站: BBS 未名空间站 (Mon May 4 17:53:30 2015, 美东)
最近看一篇文章，GPU计算的
用的deep learning
其中提到NN的计算复杂度是O(MN+LN^2)
M是输入的unit，N是所有layer的hidden unit，L是layer数
然后用GPU并行之后，就是M，N的linear时间复杂度了？
说原因是，计算两个N dimension vector的内积，用CPU是O(N)的，用GPU是O(1)
这是鬼扯吧？
我怀疑实际原因是，他们的GPU平台有近3K个core，计算中M在2000左右，N在几千数量级
所以他们是用core的数量K 抵消的一个N的复杂度
大家看是不是这样？ |
|
w******1
发帖数: 520 | 6 有1,2,....一直到n的无序数组，求排序算法，并且要求时间复杂度为O(n)，空间复杂
度O(1)，使用交换，而且一次只能交换两个数.（华为）
分析：数组的特点是值和下标满足一定的关系，以此作为交换的终止条件。
但这个算法的时间复杂度如何证明是O(n)呢？
#include
int main()
{
int a[] = {10,6,9,5,2,8,4,7,1,3};
int len = sizeof(a) / sizeof(int);
int temp;
for(int i = 0; i < len; )
{
if ( a[i] != i + 1)//下标和值不满足对应关系
{
temp = a[a[i] - 1]; //不相等的话就把a[i]交换到与索引相应的位置
a[a[i] - 1] = a[i];
a[i] = temp;
}
else
i++; // 保存，以后此值不会再动了
}
for (int j = 0; j < len; j++)
cout<
return 0;
} |
|
f****4
发帖数: 1359 | 7 如果用heap实现的话，这个时间复杂度怎么算？
O(n)? 还是O(n+n*logk)->O(n*logk)？
之前算时间复杂度，都是把程序各个部分需要run多少步加起来然后算big O
但是又看到说树遍历的是O(n)说是stack操作，不用计算时间复杂度，那如果是那样的
话，k个最大数就是O(n)
谁能解释一下，到底是那种算法？
谢谢 |
|
s*****t
发帖数: 11 | 8 堆排序算法如下
HEAPSORT(A)
1 BUILD-MAX-HEAP(A)
2 for i = A.size downto 2
3 exchange A[1] with A[i]
4 A.size = A.size - 1
5 MAX-HEAPIFY(A, 1)
算法书上说
1 BUILD-MAX-HEAP(A) 的时间复杂度为 O(N)
5 MAX-HEAPIFY(A, 1) 的时间复杂度为 O(lg N), N 为当时 A 的长度
那么, 整个算法的时间复杂度是
O(N) + O(lg(N-1)) + O(lg(N-2)) + ... O(1)
= O(N + lg(N-1) + lg(N-2) + ... 1)
= O(N + lg(N-1)!)
= O(lgN!)
比快速排序的 O(NlgN) = O(lg(N^N)) 还要快?
迷惑了,求大牛指点. |
|
c********t
发帖数: 5706 | 9 第一种算法，空间复杂度应该是指数级吧？
第二种算法，空间复杂度应该是O（n)吧？每个顶点都要算一次height吧。recursion
method 被调用n-1次，空间复杂度应该是O（n)吧？ |
|
h****n
发帖数: 1093 | 10 递归树有多少层空间复杂度就是多少，和时间复杂度相比，递归的空间复杂度一般是很
低的 |
|
e******i
发帖数: 106 | 11 这是在career cup 上看到的题：
Given a hashmap M which is a mapping of characters to arrays of substitute
characters, and an input string S, return an array of all possible mutations
of S (where any character in S can be substituted with one of its
substitutes in M, if it exists).
What is the time complexity? What is the space complexity? Can you optimize
either?
Example input:
M = { f: [F, 4], b: [B, 8] }
S = fab
Expected output:
[fab, Fab, 4ab, faB, FaB, 4aB, fa8, Fa8, 4a8]
这是我的解法，用backtrack... 阅读全帖 |
|
a*****u
发帖数: 1712 | 12 时间复杂度我跟你想的一样。
空间复杂度好像不对，recuision最深是k层，recursive部分空间复杂度应该是O(k)
★ 发自iPhone App: ChineseWeb 7.8 |
|
a*****u
发帖数: 1712 | 13 时间复杂度我跟你想的一样。
空间复杂度好像不对，recuision最深是k层，recursive部分空间复杂度应该是O(k)
★ 发自iPhone App: ChineseWeb 7.8 |
|
|
a***e
发帖数: 413 | 15 下面这两个1.2.写法都是O（N^2)吧？为啥2说是O（N）呢？另外，看到lc上一个
discussion的iterative的解法3.https://oj.leetcode.com/discuss/2297/the-
iterative-solution-is-easier-than-you-think
时间复杂度是O（N）吧？
我看了helper的function signature能写出1，对2中用到的好多STL要搜索才能写出来
，不熟。
Binary tree和recursion现在是我最弱处，多谢！
1.
class Solution {
public:
TreeNode *buildTree(vector &preorder, vector &inorder) {
if (preorder.size()==0) return NULL;
else if (preorder.size()==1)
{
TreeNode *t = new TreeNode(preorder[0])... 阅读全帖 |
|
j**********3
发帖数: 3211 | 16 dfs 复杂度多少？因为每个'.'，都要dfs一下，所以肯定有个mn， 但每次dfs复杂度多
少？
ii 的复杂度是多少？怎么比 i 要优化了？ |
|
k*******2
发帖数: 4163 | 17 这是算法课没及格的说法吧。
并行再牛，也不能改变计算复杂度，因为计算复杂度是以N->无穷的极限情况来讨论的
。这种情况下任何有限的core都可以忽略不计。
唯一能改变计算复杂度的是发明一个新的更高效的算法。 |
|
s*****i
发帖数: 37 | 18 【 以下文字转载自 EE 讨论区 】
发信人: scutgui (scutgui), 信区: EE
标 题: 关于markov decision process求解的复杂度 (转载)
发信站: BBS 未名空间站 (Sun Nov 27 18:32:57 2011, 美东)
发信人: scutgui (scutgui), 信区: Mathematics
标 题: 关于markov decision process求解的复杂度
发信站: BBS 未名空间站 (Sun Nov 27 18:30:58 2011, 美东)
给位大侠。小弟不才，从事工程，现开始接触MDP，大致工程类的文章都会说MDP有一个
curse of dimensionality，也就是求解的时候复杂度非常大。不知到现在为止，这样
的问题是否已经解决？
小弟数学不好，各位请拍砖。
非常感谢。 |
|
n******7
发帖数: 12463 | 19 最近看一篇文章，GPU计算的
用的deep learning
其中提到NN的计算复杂度是O(MN+LN^2)
M是输入的unit，N是所有layer的hidden unit，L是layer数
然后用GPU并行之后，就是M，N的linear时间复杂度了？
说原因是，计算两个N dimension vector的内积，用CPU是O(N)的，用GPU是O(1)
这是鬼扯吧？
我怀疑实际原因是，他们的GPU平台有近3K个core，计算中M在2000左右，N在几千数量级
所以他们是用core的数量K 抵消的一个N的复杂度
大家看是不是这样？ |
|
h******g
发帖数: 33 | 20 【 以下文字转载自 EE 讨论区 】
发信人: hustwang (子子), 信区: EE
标 题: 请问一般凸优化中的内点算法复杂度是多少？
发信站: BBS 未名空间站 (Sat Mar 7 21:53:29 2009)
比如：有N个优化变量，那么复杂度的具体表达式是什么样的？
另外，经典的water-filling算法复杂度具体表达式是什么样的？假如有N个优化变量的
话。
谢谢 |
|
b*********n
发帖数: 1258 | 21 对，算单个的F(n)
电话面试让我口述recursive算法程序，
然后跟着问我复杂度
我就不是很明白recursive算法的复杂度 |
|
B*****t
发帖数: 335 | 22 i每次增加1至少会排好一个数， i取值从0到n-1， 复杂度O(n) |
|
g*****i
发帖数: 2162 | 23 对两个k bit的数做& | ^ 复杂度是O(K)?
i>>t 的复杂度是O(t)吗?
谢谢. |
|
c*********t
发帖数: 2921 | 24 问用recursive求fib(n)的复杂度,是不是和求fib(n)值本身的方法一样？
两种方法：
1.数学表达式：用特征值
fib本身F(n) = F(n-1) + F(n-2), F(0) = 0, F(1) = 1
复杂度T(n) = T(n-1) + T(n-2), T(0) = 1, T(1) = 1
这两个的特征值都一样，就是因为初始值不一样，所以最后的系数不一样，对吧？
2. 如果用logn的方法，也可以，区别还是初始值，对吧？
谢谢！ |
|
c****p
发帖数: 6474 | 25 logk的时间复杂度和O(1)的空间复杂度就够了吧。。。 |
|
h****n
发帖数: 1093 | 26 二分的复杂度也是O（n×m）吧
两两比较 N/2 + N/4 + N/8 + ...+ 1 = N
复杂度还是O（N×M）啊
你怎么个二分的 |
|
h****n
发帖数: 1093 | 27 你的M是指什么呀，我的M是指字符串的长度 avg M是指字符串的平均长度
具体M是多少和你字符串的排列是有关系的
考虑两种极端的情况，假设所有字符串的字符都是同一个字符，
第一种所有字符按照长度从长排到短，那么比较下来的长度就是AVG M
第二种就是所有字符按照长度从短到长排，那么比较下来的长度就是MIN M
divide conquer的复杂度可以用主定理来分析的，主要看最终的复杂度看分支数量，子
问题规模和合并操作的开销
T（n）=a(T/b) + O(n^d)
T（n）= n^d if d > logb a
= n^(logb a) if d < logb a
= n^d * lgn if d == logb a |
|
c********t
发帖数: 5706 | 28 请问用了递归以后，怎么计算空间复杂度？
比如说permution和二叉树preorder遍历吧，怎么计算空间复杂度是多少呢 |
|
c********t
发帖数: 5706 | 29 同意，请空间复杂度是不是也是2^(m+n)，因为每次调用都要存m,n在stack里？ |
|
c********t
发帖数: 5706 | 30 问个弱问题。
如果一个recursion使用O(1)空间，在执行过程中，它调用了自己n次，请问空间复杂度
是不是就是O(n)? 如果它使用了O(m)空间，是不是最后空间复杂度为O(m*n)? |
|
c***s
发帖数: 192 | 31 我觉得这个解有问题，倒不是空间复杂度高。
而是时间复杂度太高了，是O(n^2).
但其实有O(n)的解法。 |
|
l*******s
发帖数: 1258 | 32 Given a string containing only digits, restore it by returning all possible
valid IP address combinations.
For example:
Given "25525511135",
return ["255.255.11.135", "255.255.111.35"]. (Order does not matter)
做完了，也基本bug free。但是比较迷惑于复杂度。
用递归的话，这个复杂度是多少？O(n平方)?
thx！ |
|
l*******s
发帖数: 1258 | 33 主要是这个玩意 每个ip的小段有个数 一共四个ip小段
暴力解的话，四个for循环，每个for循环操作3个数，复杂度就是3^4，常数啊。。。
那么递归的复杂度呢？也是3^4常数？ |
|
c*******r
发帖数: 309 | 34 public class LowestCommonAncestor {
public boolean cover(Node root, Node node) {
if (root == null)
return false;
if (root == node)
return true;
return cover(root.left, node) || cover(root.right, node);
}
public Node Ancestor(Node root, Node node1, Node node2) {
if (root == null)
return root;
if (cover(root.left, node1) && cover(root.left, node2))
return Ancestor(root.left, node1, node2);
i... 阅读全帖 |
|
c*******r
发帖数: 309 | 35 这个average复杂度难道不是O(logN*logN)？ cover()复杂度logN, recursion logN次
（层数). worse case是O(N2) |
|
w*******r
发帖数: 277 | 36 第二版的11.2里对于chaining的search hit复杂度的证明是不是太奇怪了
就是定理11.3的证明，觉得很别扭阿
为什么要假设不是事先给定了一个固定的hash table
而是假设成通过每次search miss之后insert而建立起来的？这样还要把建表的过程考
虑到概率里面去
上面在证明search miss的时候的复杂度时，就没有这么假设，而是假设事先给定的一
个hash table
两种情况采用的标准不一致阿 |
|
W********e
发帖数: 45 | 37 我的办法就是进行二分，将k个链表分为两个一组，组内进行merge。形成一个新的链表
集合。继续两个一组merge，这样下去一共会进行logk次merge，最后merge成为一个链
表。这里用的辅助函数是mergeSortedList，合并两个有序链表，这个辅助函数复杂度
应该是O(n)。
我觉得这个算法的总时间复杂度是O(nlogK),大家觉得对吗？？
class Solution {
public:
ListNode* mergeSortedList(ListNode*l1,ListNode*l2)
{
ListNode *h1=l1,*h2=l2;
ListNode *newHead=new ListNode(0),*dummy=newHead; //newHead要赋
值，否则没有next。如果是C语言的话可以申请stack的对象
if(l1==NULL&&l2==NULL)
return NULL;
while(h1!=NULL&&h2!=NU... 阅读全帖 |
|
c*******r
发帖数: 309 | 38 public boolean cover(Node root, Node node) {
if (root == null)
return false;
if (root == node)
return true;
return cover(root.left, node) || cover(root.right, node);
}
public Node Ancestor(Node root, Node node1, Node node2) {
if (root == null)
return root;
if (cover(root.left, node1) && cover(root.left, node2))
return Ancestor(root.left, node1, node2);
if (cover(root.right, node1) && cover(roo... 阅读全帖 |
|
j******2
发帖数: 362 | 39 如果是有duplicate这种情况，每个元素可用次数不大于出现次数，那complexity就c1*
c2*c3...*cn，n是可选unique元素个数，ci=元素i的个数+1。不知道变成O()怎么写？
比如{1,2,3,4,5,6}就是2^6，{1,1,1,1,1,1}就是6。
如果没有duplicate，但是每个元素可用无限次，这个复杂度怎么算阿？难道是
O(m^n)?m=target/最小元素。
两个总的说来都是指数复杂度吧？
有人有兴趣讨论下不？ |
|
j****y
发帖数: 684 | 40 首先是一个recursion算法的空间复杂度是否要考虑这个系统内部的stack深度
假如对同一个问题，算法A是recursion的，其所用的系统内部stack的深度是logn，
算法B是iterative的，其比如用了一个额外空间n，那么能说A的复杂度低吗？
因为实际上，recursion应该要存很多东西到stack里面吧 |
|
|
h**o
发帖数: 548 | 42 Given a 2D board and a word, find if the word exists in the grid.
The word can be constructed from letters of sequentially adjacent cell,
where "adjacent" cells are those horizontally or vertically neighboring. The
same letter cell may not be used more than once.
我知道有人问过了。没答案。
我觉得time 复杂度是m*n*4^(k-1). 也就是m*n*4^k.
m X n is board size, k is word size.
space 复杂度 是： 4^k (recursive)+ m*n (to mark visited board cell)
是这样吗？ |
|
h**o
发帖数: 548 | 43 Given a 2D board and a word, find if the word exists in the grid.
The word can be constructed from letters of sequentially adjacent cell,
where "adjacent" cells are those horizontally or vertically neighboring. The
same letter cell may not be used more than once.
我知道有人问过了。没答案。
我觉得time 复杂度是m*n*4^(k-1). 也就是m*n*4^k.
m X n is board size, k is word size.
space 复杂度 是： 4^k (recursive)+ m*n (to mark visited board cell)
是这样吗？ |
|
b****z
发帖数: 176 | 44 用queue 做树的广度优先遍历，空间复杂度是多少？
感觉好像不是O(n), 应该会比O(n)小？ 因为 空间复杂度应该是 树的底部的节点的数
量，因为每次都会dequeue。
大家觉得呢？ |
|
A*********c
发帖数: 430 | 45 不可能是n^2.
写出复杂度方程T(n) = 2 * sum_i (T(N-i) + T(i))
想象一下recursion tree, worst case至少是exp的复杂度。 |
|
d********i
发帖数: 582 | 46 两种做法O(1)空间复杂度是直接修改input。 而O(n)空间复杂度不修改input。
大家用哪种？ 我感觉只修修改input作为result, 好像不太合适吧！ 谢谢。 |
|
a********e
发帖数: 53 | 47 class Solution {
public:
Write a function to find the longest common prefix string amongst an array
of strings.
The Time complexity is O(logM * N), while M is the size of strs, N is the
shortest length of the str in the strs
而我觉得这个时间复杂度应该是O(MN). 因为isEqual（）的复杂度应该是O(M), as T(M
) = 2T(M/2) + O(1). 谢谢。
============================
bool isEqual(vector &strs, int index, int start, int end) {
if(end < start) return true;
if(end == start) {
if(strs[start].size() > index) return ... 阅读全帖 |
|
a********m
发帖数: 15480 | 48 复杂度效率和overhead效率是两码事。复杂度效率当然需要知道。 |
|
a********e
发帖数: 53 | 49 还有valid的时间复杂度呢？这题我看到有的博客里说复杂度是O(2^n), 因为有 n &#
8722; 1 个地方可以砍断,每个地方可断可不断。 |
|
s**********g
发帖数: 14942 | 50 用DP吧
很直观的复杂度
没记错的话就是O(mn)
你给的这个，还要调用O(n)的substring，把整个复杂度分析搞复杂了
leetcode- |
|
