Revision as of 01:00, 7 May 2011 edit SineBot (talk \| contribs) Bots 2,564,671 edits m Signing comment by 93.138.47.91 - "→Mistake in the Algorithm?: new section" ← Previous edit		Revision as of 22:14, 9 December 2011 edit undo UKoch (talk \| contribs) Extended confirmed users 2,904 edits →\|G\| in time complexity: new section Next edit →
Line 97: if the second index denotes the length of a span. <span style="font-size: smaller;" class="autosigned">—Preceding [[Wikipedia:Signatures\|unsigned]] comment added by [[Special:Contributions/93.138.47.91\|93.138.47.91]] ([[User talk:93.138.47.91\|talk]]) 00:58, 7 May 2011 (UTC)</span><!-- Template:UnsignedIP --> <!--Autosigned by SineBot--> == \|G\| in time complexity == I'm not aware of any literature that mentions \|G\|. Of course the actual time the algorithm takes depends on the "size" of the grammar (I assume \|G\| is supposed to be the number of productions), but in this kind of problem, I've only ever seen n mentioned. In particular, in the pseudocode given, the loop over all productions is unnecessary, or at least unnecessarily specific: One would implement that as a hash table lookup, which is much faster. -- My point: If nobody disagrees, I'll erase the \|G\| part. -- [[User:UKoch\|UKoch]] ([[User talk:UKoch\|talk]]) 22:14, 9 December 2011 (UTC)

Talk:CYK algorithm: Difference between revisions