我有一个家庭作业问题如下(请注意,我不是在寻找确切的答案,只是寻找简单的建议继续前进).
S是在时间<= T(n)中支持Insert(x,S),Delete(x,S)和Find_Smallest_Item(S)的数据结构.证明T(n)的下界,例如Ω(logn).
到目前为止,我的想法是:
我想我需要找到一个减少,我将把这个问题简化为一个更简单的问题,并证明它不能低于logn.我阅读了许多关于下界的教程,其中大多数将问题简化为排序,然后他们使用排序作为黑盒子并证明算法不能低于nlogn.
但是在这里,我们正在处理logn,我不知道这样的算法要减少到.也许它必须对树结构的深度做一些事情,登录.但我无法弄清楚从哪里开始.
你能给我一些提示吗？
编辑:其实我想到了一些东西,但我不知道我是否应该用这样的伎俩证明一个下限.所以,我假设我有insert,delete和find_smallest操作,每个操作都有一个logn时间复杂度.
例如,要构造一个排序列表,我可以使用delete和find_smallest函数,例如我可以第一次运行find_smallest,并在找到列表中的最小元素后,然后我将删除该元素.我将再次运行它,因此我将找到第二个最小的元素,依此类推.
因此,我可以使用delete和find_smallest函数实现排序.因此,如果我继续这样做n次,它们中的每一个都将记录(删除)+ logn(用于查找最小值),因此总体而言,排序将采用nlogn.
不过,我不知道如何调整它以进行插入.
编辑2:为了使用插入证明:在列表中找到第i个最小元素后,如果我将其插入第i个位置怎么办？例如,在通过上述过程找到第3个最小元素之后,我可以将其插入数据结构的第3个索引.因此,最后我将获得一个排序的数据结构.
我正在做学校运动,我无法想象如何做一件事.对于我所读到的,扫描仪不是最好的方法,但由于教师只使用扫描仪,这必须使用扫描仪完成.
这就是问题.用户将文本输入到数组.此数组最多可以有10行,用户输入以空行结束.
我这样做了:
String[] text = new String[11]
Scanner sc = new Scanner(System.in);
int i = 0;
System.out.println("Please insert text:");
while (!sc.nextLine().equals("")){
text[i] = sc.nextLine();
i++;
}
但这不能正常工作,我无法弄明白.理想情况下,如果用户输入:
This is line one
This is line two
现在按回车键,打印它应该给出的数组:
[This is line one, This is line two, null,null,null,null,null,null,null,null,null]
你能帮助我吗？
我试图从网页上逐页获取一些信息,基本上就是我所做的:
import mechanize
MechBrowser = mechanize.Browser()
Counter = 0
while Counter < 5000:
Response = MechBrowser.open("http://example.com/page" + str(Counter))
Html = Response.read()
Response.close()
OutputFile = open("Output.txt", "a")
OutputFile.write(Html)
OutputFile.close()
Counter = Counter + 1
好吧,上面的代码最终抛出了"Out of Memory"错误,在任务管理器中它显示该脚本在运行几个小时后耗尽了近1GB的内存......怎么回事？!
有人会告诉我出了什么问题吗？
我正在使用带有大型LaTeX Sweave文档的cacheSweave.而不是放
<<cache=true>>=
...snip...
@
在我几乎所有的代码块中,我宁愿cache=true成为默认代码,也可以使用
<<cache=false>>=
...snip...
@
当我不想要缓存代码块时.如何为代码块设置此默认参数？
我目前正在使用以下代码来编译Sweave文档:
library(cacheSweave)
Sweave(infile, driver = cacheSweaveDriver)
def f2(L):
sum = 0
i = 1
while i < len(L):
sum = sum + L[i]
i = i * 2
return sum
设n是传递给该函数的列表L的大小.以下哪项最准确地描述了此函数的运行时如何随着n的增长而增长？
(a)它像n那样线性增长.(b)它以二次方式增长,就像n ^ 2一样.
(c)它的增长小于线性.(d)增长超过二次方.
我不明白你是如何弄清楚函数的运行时和n的增长之间的关系的.有人可以向我解释一下吗？
我有一个ArrayList,里面有17,000个单词.我只需要在列表中添加一个单词,如果它还没有,我需要保留列表的排序顺序.即,我需要将其放入按字母顺序排列的正确位置.
我不知道如何找到插入它的正确位置.我正在使用二进制搜索来查找该单词是否已经在列表中,如果它在那里则返回索引,如果不是则返回-1.我打算使用ArrayList.add(int index,E element)将其放入.
我想传递两个矩阵作为参数.这些矩阵有不同的大小,我不明白我是如何做这项工作的:
#include <stdio.h>
#include <stdlib.h>
void f(int m[3][], int n);
int main()
{
int A[3][3]={{1,2,3},{4,5, 6},{7,8,9}};
int B[3][2]={{1,2},{3, 4}, {5, 6}};
f(A, 3);
f(B, 2);
return 0;
}
void f(int m[3][], int n)
{
int i,j;
for(i=0;i<3;i++)
{
for(j=0;j<n;j++)
printf("%5d", m[i][j]);
}
return;
}
我怎样才能做到这一点？
我真的很抱歉用一个AttributeError来打扰你,但我无法弄清楚我的代码有什么问题,尽管我已经解决了很多关于AttributeErrors的问题.
这是我的代码:
class Base:
def __init__(self):
self.window = gtk.Window(gtk.WINDOW_TOPLEVEL)
self.window.set_position(gtk.WIN_POS_CENTER)
self.window.set_size_request(500,500*9/16)
self.window.set_title("pattern_executer")
self.button1 = gtk.Button(" E x i t ")
self.button1.connect("clicked",self.close)
self.button2 = gtk.Button("Plot")
self.button2.connect("clicked",self.plot)
self.button3 = gtk.Button("Search")
self.button3.connect("clicked",self.search)
self.entry1 = gtk.Entry()
self.entry1.connect("changed",self.dir_ch)
self.entry1.set_text("dir1")
self.entry2 = gtk.Entry()
self.entry2.connect("changed",self.dir_ch)
self.entry2.set_text("name")
self.entry3 = gtk.Entry()
self.entry3.connect("changed",self.dir_ch)
self.entry3.set_text("dir2")
#self.label1 = gtk.Label("FUNCTIONS")
fixed1 = gtk.Fixed()
fixed1.put(self.button1,10,250)
fixed1.put(self.button2,10,60)
fixed1.put(self.button3,10,30)
fixed1.put(self.entry1,90,30)
fixed1.put(self.entry2,90,60)
fixed1.put(self.entry3,90,90)
self.window.add(fixed1)
self.window.show_all()
self.window.connect("destroy",self.close)
def run(self,widget):
print "Run ... "
def search(self,widget):
box = (settings[1] - settings[3]/2,settings[2] - settings[4]/2,settings[1] + settings[3]/2,settings[2] + settings[4]/2)
cut1 = …我正在学习 coursera NLP 课程，第一个编程任务是构建 Viterbi 解码器。我想我真的快要完成它了，但是有一些我似乎无法追踪的难以捉摸的错误。这是我的代码：
http://pastie.org/private/ksmbns3gjctedu1zxrehw
http://pastie.org/private/ssv6tc8dwnamn2qegdvww
到目前为止，我已经调试了与“教学”相关的函数，所以我可以说算法的参数正在被正确估计。特别感兴趣的是 viterbi() 和 findW() 方法。我正在使用的算法的定义可以在这里找到：http : //www.cs.columbia.edu/~mcollins/hmms-spring2013.pdf第 18 页。
我很难理解的一件事是，当 K = {1, 2} 时，我应该如何更新特殊情况的反向指针（在我的情况下，这是 0 和 1，因为我是零-索引我的数组）分别在这些情况下我使用的参数是 q({TAGSET} | *, *) 和 q ({TAGSET} | *, {TAGSET})。
提示而不是勺子喂的答案也将受到高度赞赏！
当我使用R的p.adjust函数来计算错误发现率时,我似乎得到了不一致的结果.基于所引用的纸张文档 经调整的p值应该这样来计算:
adjusted_p_at_index_i= p_at_index_i*(total_number_of_tests/i).
现在,当我跑步时,p.adjust(c(0.0001, 0.0004, 0.0019),"fdr")我得到了预期的结果
c(0.0003, 0.0006, 0.0019)
但是当我跑步时,p.adjust(c(0.517479039, 0.003657195, 0.006080152),"fdr")我得到了这个
c(0.517479039, 0.009120228, 0.009120228)
而不是我计算的结果:
c(0.517479039, 0.010971585, 0.009120228)
R对可以解释这两种结果的数据做了什么？