Steven D'Aprano wrote:
Secondly, O(N*log N) applies to *comparison sorts*. Non-comparison sorts
such as radix-, counting- and bucket-sort have average case complexity of
O(N).
They require additional space, though.
--
Greg
--
https://mail.python.org/mailman/listinfo/python-list
On 02/10/2014 04:20 AM, Sturla Molden wrote:
In general, we cannot sort a sequence in O(n) time. O(n log n) is the lower
bound on the complexity.
Only true for sorting that involve comparison. However, sorts that use
the values of the inputs as positional keys have a lower bound
complexity (om
On Mon, 10 Feb 2014 10:20:33 +, Sturla Molden wrote:
> Wesley wrote:
>> [Wesley] This is not homework:-)
>> And actually I am new to algorithm, so you guys can feel free to say
>> anything you want
>
> In general, we cannot sort a sequence in O(n) time. O(n log n) is the
> lower bound on the
Chris Angelico wrote:
mylist = reorder_generator(mylist)
You can iterate over it, but can't index it. But hey, it complies with
the space/time requirements!
Rather than a generator, you could use a view object
that rearranges the indices when you access an element.
That would comply with the s
On 10 February 2014 15:52, Chris Angelico wrote:
> On Tue, Feb 11, 2014 at 2:45 AM, Oscar Benjamin
> wrote:
>> Something like
>>
>> mylist[:] = reorder_generator(mylist)
>>
>> won't work because the generator would need to access the data
>> non-sequentially (it would need to read elements af
On Tue, Feb 11, 2014 at 2:45 AM, Oscar Benjamin
wrote:
> Something like
>
> mylist[:] = reorder_generator(mylist)
>
> won't work because the generator would need to access the data
> non-sequentially (it would need to read elements after they were
> overwritten).
This would have O(1) space an
On 10 February 2014 15:03, Sturla Molden wrote:
> Chris Angelico wrote:
>
>> That's assuming it really is a sort operation. The problem description
>> isn't entirely clear on this point, but if it's actually a zip, then
>> it can definitely be done in O(n).
>
> Ah, I didn't read it carefully enou
On Tue, Feb 11, 2014 at 2:03 AM, Sturla Molden wrote:
> Chris Angelico wrote:
>
>> That's assuming it really is a sort operation. The problem description
>> isn't entirely clear on this point, but if it's actually a zip, then
>> it can definitely be done in O(n).
>
> Ah, I didn't read it carefull
Chris Angelico wrote:
> That's assuming it really is a sort operation. The problem description
> isn't entirely clear on this point, but if it's actually a zip, then
> it can definitely be done in O(n).
Ah, I didn't read it carefully enough. :-)
Granted, a zip can be done in O(n) time and O(1)
On Mon, Feb 10, 2014 at 9:20 PM, Sturla Molden wrote:
> Wesley wrote:
>> [Wesley] This is not homework:-)
>> And actually I am new to algorithm, so you guys can feel free to say
>> anything you want
>
> In general, we cannot sort a sequence in O(n) time. O(n log n) is the lower
> bound on the co
Wesley wrote:
> [Wesley] This is not homework:-)
> And actually I am new to algorithm, so you guys can feel free to say anything
> you want
In general, we cannot sort a sequence in O(n) time. O(n log n) is the lower
bound on the complexity.
--
https://mail.python.org/mailman/listinfo/python-l
Wesley Wrote in message:
>
>> > here is input sequence like a1,a2,...,an,b1,b2,...,bn ï¼the ax and bx
>> > always exist in pair. So, now, how to change the sequence to
>> > a1,b1,...,an,bn, with time complexity as O(n) and space as O(1).
>>
>>
>>
>> The two halves of the list are already s
[Wesley] This is not homework:-)
And actually I am new to algorithm, so you guys can feel free to say anything
you want
--
https://mail.python.org/mailman/listinfo/python-list
> > here is input sequence like a1,a2,...,an,b1,b2,...,bn ，the ax and bx always
> > exist in pair. So, now, how to change the sequence to a1,b1,...,an,bn, with
> > time complexity as O(n) and space as O(1).
>
>
>
> The two halves of the list are already sorted, yes?
[Wesley] No, not sorted
在 2014年2月9日星期日UTC+8下午11时48分17秒，Oscar Benjamin写道：
> Please don't top-post.
>
> On Feb 9, 2014 2:40 PM, "Ni Wesley" wrote:
>
> >
>
> > Yes, with no new list, otherwise, space won't to be O(1)
>
> Did you read the link I posted:
>
> >> http://en.wikipedia.org/wiki/In-place_matrix_transposition
>
In article <52f80bca$0$29972$c3e8da3$54964...@news.astraweb.com>,
Steven D'Aprano wrote:
> On Sun, 09 Feb 2014 10:05:02 -0500, Roy Smith wrote:
>
> > Is this a homework problem?
>
> and then (paraphrasing):
>
> > working code that solves the problem
>
> /headdesk
I gave him the benefit of t
On Sun, 09 Feb 2014 10:05:02 -0500, Roy Smith wrote:
> Is this a homework problem?
and then (paraphrasing):
> working code that solves the problem
/headdesk
--
Steven
--
https://mail.python.org/mailman/listinfo/python-list
On Sun, 09 Feb 2014 04:13:50 -0800, Wesley wrote:
> Hi guys,
>Here is one question related to algorithm.
> Details here:
>
> here is input sequence like a1,a2,...,an,b1,b2,...,bn ，the ax and bx
> always exist in pair. So, now, how to change the sequence to
> a1,b1,...,an,bn, with time complex
Please don't top-post.
On Feb 9, 2014 2:40 PM, "Ni Wesley" wrote:
>
> Yes, with no new list, otherwise, space won't to be O(1)
Did you read the link I posted:
>> http://en.wikipedia.org/wiki/In-place_matrix_transposition
Oscar
--
https://mail.python.org/mailman/listinfo/python-list
In article ,
Wesley wrote:
> Hi guys,
>Here is one question related to algorithm.
> Details here:
>
> here is input sequence like a1,a2,...,an,b1,b2,...,bn ï¼the ax and bx always
> exist in pair. So, now, how to change the sequence to a1,b1,...,an,bn, with
> time complexity as O(n) and s
Yes, with no new list, otherwise, space won't to be O(1)
Wesley
2014年2月9日 下午10:31于 "Oscar Benjamin" 写道：
> Please reply to the list rather than directly to me so that other
> people can see the answer to my question and offer you help.
>
> On 9 February 2014 14:04, Ni Wesley wrote:
> > 2014年2月9日
Please reply to the list rather than directly to me so that other
people can see the answer to my question and offer you help.
On 9 February 2014 14:04, Ni Wesley wrote:
> 2014年2月9日 下午9:41于 "Oscar Benjamin" 写道：
>
>> On 9 February 2014 12:13, Wesley wrote:
>> > Hi guys,
>> >Here is one questi
On 9 February 2014 12:13, Wesley wrote:
> Hi guys,
>Here is one question related to algorithm.
> Details here:
>
> here is input sequence like a1,a2,...,an,b1,b2,...,bn ，the ax and bx always
> exist in pair. So, now, how to change the sequence to a1,b1,...,an,bn, with
> time complexity as O(
On Sun, Feb 9, 2014 at 11:13 PM, Wesley wrote:
> here is input sequence like a1,a2,...,an,b1,b2,...,bn ，the ax and bx always
> exist in pair. So, now, how to change the sequence to a1,b1,...,an,bn, with
> time complexity as O(n) and space as O(1).
The two halves of the list are already sorted,
On Sunday, February 9, 2014 2:13:50 PM UTC+2, Wesley wrote:
> Hi guys,
>Here is one question related to algorithm.
> Details here:
>
> here is input sequence like a1,a2,...,an,b1,b2,...,bn ，the ax and bx always
> exist in pair. So, now, how to change the sequence to a1,b1,...,an,bn, with
> t
Hi guys,
Here is one question related to algorithm.
Details here:
here is input sequence like a1,a2,...,an,b1,b2,...,bn ，the ax and bx always
exist in pair. So, now, how to change the sequence to a1,b1,...,an,bn, with
time complexity as O(n) and space as O(1).
Any comments will be appreciate
26 matches
Mail list logo
