Testwiki:Property proposal/algorithm complexity
algorithm complexity
This is a proposal of six related properties.
- Motivation
(Add your motivation for this property here.) GZWDer (talk) 18:53, 16 January 2017 (UTC)
- Discussion
- Template:Support best-case and worst-case property proposals. Pixeldomain (talk) 07:17, 17 January 2017 (UTC)
- Template:Comment How is "average" defined? Sum of the time taken to execute each permutation of the algorithm, divided by the total number of permutations? Is "average" defined by a probability distribution of a limited number of samples? I see a comment at English Wikipedia which indicates "average" is ambiguous, whereas "expected time complexity" is allegedly better defined. Pixeldomain (talk) 07:17, 17 January 2017 (UTC)
- Template:S --Andrawaag (talk) 09:55, 27 January 2017 (UTC)
Template:Ping project ChristianKl (talk) 11:16, 27 January 2017 (UTC)
- Template:Comment Agreed with the previous comment. Please add the relate item to the exact complexity notion associated.
- Template:Comment Datatype should be item, and the formula put in this item. It's less error prone as there is no ambiguity on the kind of "O" used in the formula and there is no risk of bad parsing later. Something like a "linear" item, or maybe "linear space". It's even possible to create items like "linear time algorithm". author TomT0m / talk page 11:43, 27 January 2017 (UTC)
- (Edited: was oppose) per TomT0m unless the data type is changed. Also do we really need 6 properties for this, isn't there another way to handle it (e.g with a qualifier?) ArthurPSmith (talk) 16:35, 27 January 2017 (UTC)
- Template:Comment en:w:Shellsort has some examples of non-simple complexities, for example:
. If this was an individual item, what would it be labelled? And how many items would need to be created to support the definition of all algorithm complexities? At the moment, I don't see how it would be practical to create an item for each complexity. Pixeldomain (talk) 01:30, 6 February 2017 (UTC)
- Template:Ping project Are there additonal comments about how this property should be created? Item or formula? ChristianKl (talk) 15:52, 16 February 2017 (UTC)
- Template:Comment Items would clearly make querying for algorithms with similar complexity easier (identifier instead of looking for a similar string). --Tobias1984 (talk) 19:55, 16 February 2017 (UTC)
- Template:Comment Template:Ping Agreed that items have theoretical benefits over formulas, but the practical outcome will be many items without meaningful labels (see my example above). How many complexity formulas will have meaningful labels in different languages? On this basis, I still think formulas may be better suited for these properties. Pixeldomain (talk) 03:12, 17 February 2017 (UTC)
- Template:Support Ok, I've been thinking about this for a bit. Template:Ping you have a good point on the number of different complexity items we might end up with. If we made them items I think you could label them by a rough verbal transcription of the formula, say "order N to the power 1 plus square root of 8 ln 5/2 over ln N" for your example. But I'm now somewhat convinced this is a good case where the math formula (with a regex to ensure consistency?) would work - so removed my "oppose" above and added support here to do these as math formulas after all. ArthurPSmith (talk) 17:01, 3 March 2017 (UTC)
- Template:Ping Template:Done ChristianKl (talk) 08:47, 8 March 2017 (UTC)