解雇6000多中小学老师会多大程度影响中文老师？ - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>Education - 教育学

解雇6000多中小学老师会多大程度影响中文老师？

解雇6000多中小学老师会多大程度影响中文老师？# Education - 教育学

s*o2010-05-08 07:05

1 楼

最近看中一个要建的房子,可以选floor plan, 选lot。以前研究了很多风水，现在很多
都变得可容忍了，比如卫生间很靠房子中间。lg不怎么笃信风水，所以他觉得无所谓
。而我风水看多了，就心里有些介意，淡又想想，如果我本来不知道，是不是就会觉得
房型很好呢。不知道这样的房子以不应该买？

q*22010-05-08 07:05

2 楼

Please give some ideas how to answer this question, thanks in advance!!
Give efficient algorithms for finding the largest k values (in order) out of
a set of n, using comparisons only (e.g. no hashing), in the case where: (a
) k = 3 (b) k = n/2; (c) k = log(n). (You can use a different algorithm for
each case.) State the asymptotic worst-case running time of your algorithms.

w*z2010-05-08 07:05

3 楼

问一下，用Intel Visual Fortran10做单机计算。以上差别大吗？

j*j2010-05-08 07:05

4 楼

有没有人知道纽约大概有多少个公立中文老师？
解雇6000纽约老师对于中文老师有多大影响？

d*r2010-05-08 07:05

5 楼

风水的作用，可以看这里
http://www.mitbbs.com/article_t/Fengshui/31161001.html
卫生间靠中间，风水上来说是不好。不过现代这么多卫生间都在中间的，也没见出什么
大事啊。为什么呢？究其原因，古时候厕所是家里最脏最不卫生的地方，是以说放在房
子中间必然影响整个住家的感觉，而现在科技上来了，条件好了，卫生间也能搞得很整
洁，所以现在的影响不会有旧社会那么大了。风水也是一门学问也该与时俱进的。

【在 s*****o 的大作中提到】

: 最近看中一个要建的房子,可以选floor plan, 选lot。以前研究了很多风水，现在很多
: 都变得可容忍了，比如卫生间很靠房子中间。lg不怎么笃信风水，所以他觉得无所谓
: 。而我风水看多了，就心里有些介意，淡又想想，如果我本来不知道，是不是就会觉得
: 房型很好呢。不知道这样的房子以不应该买？

w*g2010-05-08 07:05

6 楼

看大家都不吱声，我来抛砖引玉。我其实没什么好的算法。我觉得就是需要O(nlog k)。
第三种情况可能有巧妙的办法，但是前两种情况没什么好说的：
k = 3: O(n), 好歹每个数都要看一遍吧。
k = n/2: O(nlogn)，因为k = n/2的复杂度和k = n其实是一样的，而排序n个数需要O(
nlogn)。

of
(a
for
algorithms.

【在 q****2 的大作中提到】

: Please give some ideas how to answer this question, thanks in advance!!
: Give efficient algorithms for finding the largest k values (in order) out of
: a set of n, using comparisons only (e.g. no hashing), in the case where: (a
: ) k = 3 (b) k = n/2; (c) k = log(n). (You can use a different algorithm for
: each case.) State the asymptotic worst-case running time of your algorithms.

S*12010-05-08 07:05

7 楼

解雇老师，偶觉得2个方向，一个是公立学校班级变大，另一个就是有些选修课可以不
开设，比如中文。

t*t2010-05-08 07:05

8 楼

这问题问的不清楚啊, 有多少空间限制, 能不能改原数, 都影响算法的嘛.

of
(a
for
algorithms.

【在 q****2 的大作中提到】

y*n2010-05-08 07:05

9 楼

serious?

【在 j**j 的大作中提到】

: 有没有人知道纽约大概有多少个公立中文老师？
: 解雇6000纽约老师对于中文老师有多大影响？

j*e2010-05-08 07:05

10 楼

理论上效率最高的检索是哈希吧。
基于树的应该是b-tree吧？

L*k2010-05-08 07:05

11 楼

en !

【在 S*********1 的大作中提到】

: 解雇老师，偶觉得2个方向，一个是公立学校班级变大，另一个就是有些选修课可以不
: 开设，比如中文。

c*t2010-05-08 07:05

12 楼

Assuming this "set" is randomly ordered and no constraint on the algorithm.
a. O (n). Has to spend O (n) time to scan. Sorting 3 numbers is O (1).
So overall O (n).
b. O (nlogn). Getting k largest numbers from n is O (n). But sorting
these numbers using comparison only is O (nlogn). So overall O (nlogn).
c. O (n). Finding these k numbers would take O (n) time. Sorting these
numbers should take O ( log n * log log n ) < O ( log^2 n) < O ( n).
So overall is O (n).

of
(a
for
al

【在 q****2 的大作中提到】

w*g2010-05-08 07:05

13 楼

不信，给算法。

【在 c*****t 的大作中提到】

: Assuming this "set" is randomly ordered and no constraint on the algorithm.
: a. O (n). Has to spend O (n) time to scan. Sorting 3 numbers is O (1).
: So overall O (n).
: b. O (nlogn). Getting k largest numbers from n is O (n). But sorting
: these numbers using comparison only is O (nlogn). So overall O (nlogn).
: c. O (n). Finding these k numbers would take O (n) time. Sorting these
: numbers should take O ( log n * log log n ) < O ( log^2 n) < O ( n).
: So overall is O (n).
:
: of

c*t2010-05-08 07:05

14 楼

grab clrs.

【在 w***g 的大作中提到】

:
: 不信，给算法。

h*e2010-05-08 07:05

15 楼

Find the kth largest number where k = logn. O(n)
Do a scan to pick the first k largest numbers. O(n)

【在 w***g 的大作中提到】

:
: 不信，给算法。

w*g2010-05-08 07:05

16 楼

scan的话复杂度也得和k有关吧，我最多也就能想到O(nlogk)，把top k保存在堆里。不
知道你有什么更好的办法。

【在 h*******e 的大作中提到】

: Find the kth largest number where k = logn. O(n)
: Do a scan to pick the first k largest numbers. O(n)

s*u2010-05-08 07:05

17 楼

算法导论里面，找第K个数，有个分段的O(n)的方法
不过就是实际效果不理想，所以没什么人用就是了

【在 w***g 的大作中提到】

: scan的话复杂度也得和k有关吧，我最多也就能想到O(nlogk)，把top k保存在堆里。不
: 知道你有什么更好的办法。

n*e2010-05-08 07:05

18 楼

median of medians? It is a joke.

t*t2010-05-08 07:05

19 楼

partition based selection algorithm is linear on average (regardless of k).

【在 w***g 的大作中提到】

: scan的话复杂度也得和k有关吧，我最多也就能想到O(nlogk)，把top k保存在堆里。不
: 知道你有什么更好的办法。

t*t2010-05-08 07:05

20 楼

median of medians guarantees worst case linear, although no one really uses
it. (i don't think it's a joke though.)
usually partition based selection is already good enough.

【在 n****e 的大作中提到】

: median of medians? It is a joke.

g*n2010-05-08 07:05

21 楼

找到第k大的数x -- O(n)
线性扫描整个数组，选择所有比x大的数 -- O(n)
对选出的k个数排序 -- klogk

t*t2010-05-08 07:05

22 楼

in fact, when you find kth number with partition based algorithm, you
already found all number greater than it

【在 g****n 的大作中提到】

: 找到第k大的数x -- O(n)
: 线性扫描整个数组，选择所有比x大的数 -- O(n)
: 对选出的k个数排序 -- klogk

g*t2010-05-08 07:05

23 楼

可以把堆排序改一下吧。建成堆以后，只出最大的K个元素就行了。