当前位置:  编程技术>综合

[1]递归式求解-主定理

1.主定理:设a>=1和b>1为常数,设f(n)为一函数,T(n)由递归式

对非负整数定义,其中n/b指下取整或上取整.那么T(n)可能有如下的渐进界:

(1)若对于某常数 ε>0,有,则;

(2)若.则;

(3)若对于某常数 ε>0,有,且某常数 c<1与所有足够大的n,有,则

2.主定理的使用方法.

由主定理的三种情况可以看出,每一种情况都要比较 f(n) 与进行比较.(求复杂度时,通常取上界)

第一种情况,f(n)与进行比较,较大,则解为

第二种情况,两种函数同样大,这是乘以对数因子lgn,即

第三种情况,f(n)较大,则递归式的解为

3.例题示范

(1).,求这个递归式的复杂度.

第一步.计算,可求得=n^2,

第二步.与f(n)=n进行比较,因此符合第一种情况,解得

(2)

第一步.计算,可求得a=1, b=3/2,因此=

第二步.与f(n)=1进行比较,符合第二种情况,解得

(3)第三中情况和第一种类似,不再举例

(4)

第一步.计算,a=2, b=2,    = n.看上去符合第三种情况,因为f(n)=lgn渐进大于n,但是不是多项式大于. 

 对于任意正常数ε,比值f(n)与等于nlgn/n = lgn.渐进小于n^ε,(可用求极限方法分子分母同时求导求得).这种情况落在情况二和情况三之间.

这种情况下的递归式求解要用到:(算法导论4.4-2)

定理:若,其中k>=0,则主定理中递归式的解为

[2]初步接触storm

    今天学习了一下storm的相关知识，不是很深入，就是看了一下storm-starter-master项目里的WordCountTopology。直接运行报错，发现这个例子中，有个Bolts是用python或者ruby语言开发的。因为这个例子要完成的任务就是计算单词的频率，比较简单，所以打算调通它，然后把程序一步步的跟一遍，这样就好理解一些内容了。

    我的方法就是把SplitSentence的核心用java实现。

    首先肯定不用再扩展ShellBolt了，也不实现IRichBolt，而是实现BaseBasicBolt。在execute方法里的内容就照着python代码，最后一句写成
collector.emit(new Values(word,1));

但是报错：
Tuple created with wrong number of fields. Expected 1 fields but got 2 fields
说实话，我在截止错误出现的时候，对storm的理解都是相当含糊的，于是我把上面那句改成
collector.emit(new Values(word));
居然能正确运行，这纯粹是撞上的，不过这倒让我对declareOutputFields这个方法的作用有了了解。在本例中，declareOutputFields里的内容是：
declarer.declare(new Fields("word"));
它声明了该Bolt的输出字段，只有一个。如果是
declarer.declare(new Fields("word","count"));则最初的那种格式是可以的。

而且，在fieldsGrouping函数里面，还可以设定从上一个Bolt中获得哪些Fields。
我觉得写Topology就像是水管工人的工作，把水流引流到需要的地方去。

已有 0 人发表留言，猛击->>这里<<-参与讨论


ITeye推荐

• —软件人才免语言低担保 赴美带薪读研！—

[3]jQuery MiniUI 开发教程 导航控件 OutlookTree：折叠树（九）

OutlookTree：折叠树


参考示例：OutlookTree：折叠树

创建OutlookTree

<div id="leftTree" url="../data/outlooktree.txt" onnodeselect="onNodeSelect"
    textField="text" idField="id" parentField="pid">
</div>

数据格式
[
    {id: "user", text: "用户管理"},
       
    {id: "lists", text: "Lists", pid: "user" },
           
    {id: "datagrid", text: "DataGrid", pid: "lists"},           
    {id: "tree", text: "Tree" , pid: "lists"},
    {id: "treegrid", text: "TreeGrid " , pid: "lists"},
       
    {id: "layouts", text: "Layouts", expanded: false, pid: "user"},
       
    {id: "panel", text: "Panel", pid: "layouts"},
    {id: "splitter", text: "Splitter", pid: "layouts"},
    {id: "layout", text: "Layout ", pid: "layouts"},
       
    { id: "right", text: "权限管理"},
       
    {id: "base", text: "Base", expanded: false, pid: "right" },
               
    {id: "ajax", text: "Ajax", pid: "base"},
    {id: "json", text: "JSON", pid: "base"},
    {id: "date", text: "Date", pid: "base"},
       
    {id: "forms", text: "Forms", expanded: false, pid: "right"},
               
    {id: "button", text: "Button", pid: "forms"},
    {id: "listbox", text: "ListBox", pid: "forms"},
    {id: "checkboxlist", text: "CheckBoxList", pid: "forms"},
    {id: "radiolist", text: "RadioList", pid: "forms"},
    {id: "calendar", text: "Calendar", pid: "forms"}               
]



已有 0 人发表留言，猛击->>这里<<-参与讨论


ITeye推荐

• —软件人才免语言低担保 赴美带薪读研！—