[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: `completion-in-region'
From: |
Stefan Monnier |
Subject: |
Re: `completion-in-region' |
Date: |
Sun, 11 Apr 2010 22:10:50 -0400 |
User-agent: |
Gnus/5.13 (Gnus v5.13) Emacs/24.0.50 (gnu/linux) |
>> If you use ".*?a.*?b.*?c", then yes it gives the
>> same matches but it also has the same O(N^3) worst case.
> This is not the right place perhaps to educate me on this, but to me
> it looks like just three linear searches with the summed length for
> the searches equal to that of the candidate strings. Is not that O(N)?
When matched against "ababab", it will do the following:
- search for a in the string.
- for each match of a, search for b in the remaining string.
- for each match of b, search for c in the remaining string.
These are 3 nested loops, each of them doing a number of iterations
proportional to N, so you get O(N^3) complexity.
Stefan
- Re: `completion-in-region', (continued)
- Re: `completion-in-region', Leo, 2010/04/11
- Re: `completion-in-region', Stefan Monnier, 2010/04/11
- RE: `completion-in-region', Drew Adams, 2010/04/11
- Re: `completion-in-region', Stefan Monnier, 2010/04/11
- RE: `completion-in-region', Drew Adams, 2010/04/11
- Re: `completion-in-region', Stefan Monnier, 2010/04/11
- RE: `completion-in-region', Drew Adams, 2010/04/11
- Re: `completion-in-region', Lennart Borgman, 2010/04/11
- Re: `completion-in-region', Stefan Monnier, 2010/04/11
- Re: `completion-in-region', Lennart Borgman, 2010/04/11
- Re: `completion-in-region',
Stefan Monnier <=
- Re: `completion-in-region', Lennart Borgman, 2010/04/12
- Re: `completion-in-region', Stefan Monnier, 2010/04/12
- Re: `completion-in-region', Davis Herring, 2010/04/12
- RE: `completion-in-region', Drew Adams, 2010/04/11
- Re: `completion-in-region', Leo, 2010/04/12
- Re: `completion-in-region', Stefan Monnier, 2010/04/12
- Re: `completion-in-region', Leo, 2010/04/12