0

Runtime of appending items from a 2d array to a 1d list

Hello, can anyone help with the runtime/time complexity for appending all elements (using a nested loop) of a 2d array to a single list? I have been trying to find this everywhere but with very little luck

17th Dec 2020, 4:43 PM
438bebop
13 odpowiedzi
+ 2
?? Your not allowed to use 'in'? You're using 'in' for your current version. Lol Anyway, no it's not the most efficient, it's actually faster if you use the '+=' operator do to some internal optimizations of the python language. for i in range(len(A)): flat += A[i] This also removes the need for the inner loop. https://code.sololearn.com/cV5x8Emv55cr/?ref=app
17th Dec 2020, 10:29 PM
ChaoticDawg
ChaoticDawg - avatar
+ 2
Here's some info on time complexity. Your answer would depend on your code. Are you trying to flatten a list? Are you using your own algorithm to do so or using numpy/pandas? Are/Is the list(s) dimensional structure fixed and constant? (Always a list of flat lists), or is it unknown. Etc https://www.sololearn.com/learn/6362/?ref=app
17th Dec 2020, 8:12 PM
ChaoticDawg
ChaoticDawg - avatar
+ 1
That would be O(n*m) Where n is the length of the list A and m is the length of the inner list(s). It would be a close resemblance to O(n²). FYI, you don't need to use range here since A and the inner lists are iterables. for lst in A: for element in lst: flat.append(element) Here's a couple of examples, one using itertools. https://code.sololearn.com/cVahrjLtqevH/?ref=app https://code.sololearn.com/cNdGsoa4gTvs/?ref=app
17th Dec 2020, 8:36 PM
ChaoticDawg
ChaoticDawg - avatar
+ 1
Not when used in this manner. Just run the code and check the output.
17th Dec 2020, 10:32 PM
ChaoticDawg
ChaoticDawg - avatar
+ 1
Oh wow
17th Dec 2020, 10:33 PM
438bebop
+ 1
The time complexity (I'm guessing this is what you really mean, as runtime and TC aren't the same, but they are related) for flattening in this manner (keep in mind in won't work for more complex '3d' lists) is essentially O(n) where the time complexity of a typical mergesort is O(n log n). The issue is that n changes from flattening to sorting. For example if you used the matrix in my previous code, which is 5x5, (imagine it was unsorted though) for flattening n is equal to 5. Once flattened n is now 25 due to the original list having 5 lists with 5 elements each.
17th Dec 2020, 10:48 PM
ChaoticDawg
ChaoticDawg - avatar
+ 1
If n is the size of the original un-flattened list (5), Then I would say its O(n) + O(n*m log n*m), but this might just be a bit much for me to wrap my head around atm. Lol
17th Dec 2020, 11:09 PM
ChaoticDawg
ChaoticDawg - avatar
+ 1
Ha ha, thanks
17th Dec 2020, 11:10 PM
438bebop
0
Thank you. It would be something like this: def flat_matrix(A):      flat = []      for i in range(len(A)):          for j in range(len(A[i])):              flat.append(A[i][j])      return flat
17th Dec 2020, 8:18 PM
438bebop
0
Thanks, we're not allowed to use 'in' for this class I'm doing unfortunately, or anything more advanced than len, range, append. Would you say the function I provide above is the most efficient way to append the elements of a 2d array into a 1d array, from a runtime perspective?
17th Dec 2020, 8:43 PM
438bebop
0
We can use for i in range, ha ha. Don't you need an inner loop to iterate over all the elements of the 2d array?
17th Dec 2020, 10:31 PM
438bebop
0
Sorry, one more question: if I do this and then do a mergesort on flat (the resulting list), what would the runtime be?
17th Dec 2020, 10:35 PM
438bebop
0
Ok, so if the matrix is symmetrical and the rows are sorted lists, with this flattening algorithm, would that plus merge sort be O(n log n) or O(n^2 log n)?
17th Dec 2020, 10:52 PM
438bebop