1.3.8　OSNTR算法的复杂度分析

以下对本章提出的OSNTR算法的时间复杂度和空间复杂度进行分析，并将其与主题模型LDA和BTM的时间复杂度和空间复杂度进行对比。

（1）时间复杂度

LDA模型的时间复杂度为O（N iterMKl），其中N iter、M、K和l分别表示迭代次数、文档数、主题数和文档的平均长度。BTM模型的时间复杂度为O（N iterKN B），其中N B是整个语料库中双词的数量，N B=Ml（l-1）/2。OSNTR算法的时间复杂度为O（N iterK（M +1）），其中是文档中的双词的平均数量，OSNTR算法的时间复杂度可表示为O（N iterK N B），OSNTR算法的时间复杂度与BTM模型的时间复杂度相同，为LDA模型的（l-1）/2倍。

（2）空间复杂度

LDA模型的空间复杂度为MK+WK+Ml。BTM模型的空间复杂度为K+WK+N B。对于OSNTR算法，需要存储的变量包括：每个时空区域r中分配给主题k的单词数量（RK）、每个单词w分配给主题k的次数（WK）、主题时间Beta分布的两个参数（K）、每个双词的主题分布以及每个时间主题分布（2N B）。

在OSNTR算法采样过程中，需要对每个双词的主题进行采样，在采样双词的主题的同时，需要同时记录时间信息，上述操作需要存储的变量数为双词的总数的两倍。此外，在实际应用中，时空区域数量远远小于单词的数量，因此时空区域数量RK可以忽略不计，因此OSNTR算法需要存储的变量的总数为WK+K+2N B，相比BTM模型需要额外存储N B个变量。OSNTR算法和LDA模型之间的空间复杂度比较可以等价为变量Ml（l-1）/2和MK之间的比较。考虑到在线社交网络文本通常较短，l取值较小，因此，可以认为OSNTR算法与LDA模型的空间复杂度近似相等。