u*********n
发帖数: 864 | 1 for (i=0;i
for (j=0;j
xxxxxxxx
这个程序的时间复杂度是写成O(n^2)还是O(m*n)?
谢谢。很stupid的问题。 |
Q**a
发帖数: 406 | 2 严格来说是前者
后者是abuse of notation，但写成这样别人多半也能理解
【在 u*********n 的大作中提到】
: for (i=0;i: for (j=0;j: xxxxxxxx
: 这个程序的时间复杂度是写成O(n^2)还是O(m*n)?
: 谢谢。很stupid的问题。
|
w***g
发帖数: 5958 | 3 这个你给解释下吧，我经常写诸如O(k n^2 logm)之类的东西，看来贻笑大方了。
【在 Q**a 的大作中提到】
: 严格来说是前者
: 后者是abuse of notation，但写成这样别人多半也能理解
|
Q**a
发帖数: 406 | 4 一般n和m还能忍，不严格的情况下挺普遍的，都知道你想说啥
看见k就可以给你秒杀了，kn和n一点区别没有
对于后者（k）可以看大O表示法的定义：
http://en.wikipedia.org/wiki/Big_O_notation
前者（n m）是典型的abuse，大O表示法只能有一个n：
http://en.wikipedia.org/wiki/Abuse_of_notation
【在 w***g 的大作中提到】
: 这个你给解释下吧，我经常写诸如O(k n^2 logm)之类的东西，看来贻笑大方了。
|
S**I
发帖数: 15689 | 5 Dijkstra's Algorithm has complexity O(|E|+|V|log|V|), and according to you,
it's abuse.
【在 Q**a 的大作中提到】
: 一般n和m还能忍，不严格的情况下挺普遍的，都知道你想说啥
: 看见k就可以给你秒杀了，kn和n一点区别没有
: 对于后者（k）可以看大O表示法的定义：
: http://en.wikipedia.org/wiki/Big_O_notation
: 前者（n m）是典型的abuse，大O表示法只能有一个n：
: http://en.wikipedia.org/wiki/Abuse_of_notation
|
Q**a
发帖数: 406 | 6 我搞错了，wikipedia是说T(n)=O(logn) abuse，应该写成T(n) \in O(logn)
翻了一下算法导论，dijkstra那里确实也用了两个变量
但是前边chapter 3只给出了一个变量情况的正式定义
不过你这句话还是abuse，参见chapter 3, O notation一节最后一段
应该说worst-case complexity是O(xxx)...
,
【在 S**I 的大作中提到】
: Dijkstra's Algorithm has complexity O(|E|+|V|log|V|), and according to you,
: it's abuse.
|
M**u
发帖数: 10158 | 7 为什么一般complexity说是worst-case算是abuse?
you
【在 Q**a 的大作中提到】
: 我搞错了，wikipedia是说T(n)=O(logn) abuse，应该写成T(n) \in O(logn)
: 翻了一下算法导论，dijkstra那里确实也用了两个变量
: 但是前边chapter 3只给出了一个变量情况的正式定义
: 不过你这句话还是abuse，参见chapter 3, O notation一节最后一段
: 应该说worst-case complexity是O(xxx)...
:
: ,
|
Q**a
发帖数: 406 | 8 T(n) = O(g(n))——这样写是abuse
T(n) \in O(g(n))——应该这样写
以上出自wikipedia big_O_notation，算法导论里边有没有不记得了
complexity is O(xxx)——这句话是abuse
worst-case complexity is O(xxx)——应该这样说
以上出自算法导论，chapter 3，O notation最后一段
【在 M**u 的大作中提到】
: 为什么一般complexity说是worst-case算是abuse?
:
: you
|
