Reputation: 24 Tradesman
- Active Posts:
- 197 (0.1 per day)
- 21-April 09
- Profile Views:
- Last Active:
- Yesterday, 08:53 AM
- OS Preference:
- Favorite Browser:
- Who Cares
- Favorite Processor:
- Favorite Gaming Platform:
- Your Car:
- Dream Kudos:
Posts I've Made
Posted 21 Jul 2014sum(A[start:end]) takes O(end - start) time, which is O(end) in the worst case (that is the case where start stays at zero until the end). It will be executed with end taking the values 1 through n. So in total the time complexity will be O(sum end = 1 .. n: n) = O(n^2).
So I still wanted to prove this, so I refactored the code to use only one loop, but still operate using sum and a slice. This did improve the overall performance, but was still rated at O(n**2):
def solution(K, A): start = 0 count = 0 for end in xrange(1, len(A) + 1): if sum(A[start:end]) >= K: start = end count += 1 return count
So it seems this is definitely the case. Manually calculating the sum does provide a O(n) solution, though I don't really care for it.
Posted 20 Jul 2014sum(A[start:end]) takes O(end - start) time, which is O(end) in the worst case (that is the case where start stays at zero until the end). It will be executed with end taking the values 1 through n. So in total the time complexity will be O(sum end = 1 .. n: n) = O(n^2).
Thanks. Didn't think that the sum's complexity would change the algorithm complexity.
Rather than using the built-in sum() function, use a sum variable. Add the first n elements from start until end. If that is less than K, look at the end + 1 element and add it to the running total. Then look at the end + 2 element and add it to the running total if necessary. This is a linear time complexity solution.
I figured that out. I was bothered by the reported complexity, not the actual solution. That's why it's in the Computer Science forum, not the "programming help" forum for python.
Posted 12 Dec 2013I was aware there are bugs in the code, such as the edge case Salem_c mentioned. I appreciate the input, but I was only concerned about the memory usage of the code.
So to be clear, I should be calling delete working; before my function returns? Should be truncating the array of result to the length of the string? If so, how can I do that without allocating a new array (or is that not possible)?
Posted 5 Dec 2013Update: smtplib will most definitely fill the need.
Here's hoping accessing the database with go just as smoothly!
Posted 4 Dec 2013Thank you jon.kiparsky. I will check that out. Forgot to check the python built-in libraries, guess I should have assumed that was a thing
- Member Title:
- D.I.C Head
- 23 years old
- November 16, 1990
- PA, USA
When I'm not programming I am playing hockey. I normally play goalie, and I am actually pretty decent.
- Full Name:
- Cody A. Taylor
- Years Programming:
- Programming Languages:
code_m hasn't added any friends yet.