Talk:399: Travelling Salesman Problem - Revision history

172.70.91.166 at 04:17, 9 May 2024

2024-05-09T04:17:20Z

Mihail.stoian: /* Running time of Dynamic Programming has changed */ new section

2024-05-08T19:21:36Z

‎Running time of Dynamic Programming has changed: new section

162.158.58.141 at 09:35, 26 December 2016

2016-12-26T09:35:23Z

198.41.242.245 at 14:41, 27 June 2016

2016-06-27T14:41:44Z

198.41.242.245 at 08:57, 27 June 2016

2016-06-27T08:57:53Z

Flewk at 01:19, 28 December 2015

2015-12-28T01:19:14Z

Flewk at 01:18, 28 December 2015

2015-12-28T01:18:20Z

Flewk at 01:13, 28 December 2015

2015-12-28T01:13:40Z

173.245.54.28 at 03:55, 19 November 2015

2015-11-19T03:55:26Z

173.245.54.28: css be hard

2015-11-19T03:42:47Z

css be hard

← Older revision		Revision as of 04:17, 9 May 2024
Line 70:		Line 70:
	== Running time of Dynamic Programming has changed ==		== Running time of Dynamic Programming has changed ==

−	BTW The running time the dynamic programming solution, O(n^2 2^n) should be changed now: https://arxiv.org/abs/2405.03018	+	BTW The running time the dynamic programming solution, O(n^2 2^n) should be changed now: https://arxiv.org/abs/2405.03018 {{unsigned\|Mihail.stoian\|19:21, 8 May 2024}}

← Older revision		Revision as of 19:21, 8 May 2024
Line 67:		Line 67:
	:Seems your memory just dropped that log. [[Special:Contributions/198.41.242.245\|198.41.242.245]] 08:57, 27 June 2016 (UTC)		:Seems your memory just dropped that log. [[Special:Contributions/198.41.242.245\|198.41.242.245]] 08:57, 27 June 2016 (UTC)
	::Thank you to all of ye helpful contributors. I am not sure what led me to write the seed of this (tiredness?), but it is, as noted, a complete and steaming pile of rubbish. [[Duty Calls]], and so forth. I hope I have inadvertently amused someone. Possibly this is a result of abstract mathematics being learned at around four layers of abstraction. Have a good day/night. [[Special:Contributions/162.158.58.141\|162.158.58.141]] 09:35, 26 December 2016 (UTC)		::Thank you to all of ye helpful contributors. I am not sure what led me to write the seed of this (tiredness?), but it is, as noted, a complete and steaming pile of rubbish. [[Duty Calls]], and so forth. I hope I have inadvertently amused someone. Possibly this is a result of abstract mathematics being learned at around four layers of abstraction. Have a good day/night. [[Special:Contributions/162.158.58.141\|162.158.58.141]] 09:35, 26 December 2016 (UTC)
		+
		+	== Running time of Dynamic Programming has changed ==
		+
		+	BTW The running time the dynamic programming solution, O(n^2 2^n) should be changed now: https://arxiv.org/abs/2405.03018

← Older revision		Revision as of 09:35, 26 December 2016
Line 66:		Line 66:
	:Actually, it's not O(n!) that is equivalent to O(n log(n)), but O(log(n!)) is. See {{w\|Stirling formula}} for details.		:Actually, it's not O(n!) that is equivalent to O(n log(n)), but O(log(n!)) is. See {{w\|Stirling formula}} for details.
	:Seems your memory just dropped that log. [[Special:Contributions/198.41.242.245\|198.41.242.245]] 08:57, 27 June 2016 (UTC)		:Seems your memory just dropped that log. [[Special:Contributions/198.41.242.245\|198.41.242.245]] 08:57, 27 June 2016 (UTC)
		+	::Thank you to all of ye helpful contributors. I am not sure what led me to write the seed of this (tiredness?), but it is, as noted, a complete and steaming pile of rubbish. [[Duty Calls]], and so forth. I hope I have inadvertently amused someone. Possibly this is a result of abstract mathematics being learned at around four layers of abstraction. Have a good day/night. [[Special:Contributions/162.158.58.141\|162.158.58.141]] 09:35, 26 December 2016 (UTC)

@@ Line 64: / Line 64: @@
 ::2) Didn't read all of the rambling, but it seems like you believe a list can only be sorted by brute-force, going over each item and comparing it to the rest of the list. This would in fact be n!. Most sorting algorithms do not use the brute force method since humans are built to recognize patterns and come up with algorithms regarding those patterns. [[User:Flewk|Flewk]] ([[User talk:Flewk|talk]]) 01:13, 28 December 2015 (UTC)
-:Actually, it's not O(n!) which is equivalent to O(n log(n)), but O(log(n!)) is. See {{w|Stirling formula}} for details.
+:Actually, it's not O(n!) that is equivalent to O(n log(n)), but O(log(n!)) is. See {{w|Stirling formula}} for details.
 :Seems your memory just dropped that log. [[Special:Contributions/198.41.242.245|198.41.242.245]] 08:57, 27 June 2016 (UTC)

← Older revision		Revision as of 08:57, 27 June 2016
Line 63:		Line 63:
	::1) I think you might be confused on how math works. n! refers to factorial (123...n). n log n is n multiplied by the logarithm of n.		::1) I think you might be confused on how math works. n! refers to factorial (123...n). n log n is n multiplied by the logarithm of n.
	::2) Didn't read all of the rambling, but it seems like you believe a list can only be sorted by brute-force, going over each item and comparing it to the rest of the list. This would in fact be n!. Most sorting algorithms do not use the brute force method since humans are built to recognize patterns and come up with algorithms regarding those patterns. [[User:Flewk\|Flewk]] ([[User talk:Flewk\|talk]]) 01:13, 28 December 2015 (UTC)		::2) Didn't read all of the rambling, but it seems like you believe a list can only be sorted by brute-force, going over each item and comparing it to the rest of the list. This would in fact be n!. Most sorting algorithms do not use the brute force method since humans are built to recognize patterns and come up with algorithms regarding those patterns. [[User:Flewk\|Flewk]] ([[User talk:Flewk\|talk]]) 01:13, 28 December 2015 (UTC)
		+
		+	:Actually, it's not O(n!) which is equivalent to O(n log(n)), but O(log(n!)) is. See {{w\|Stirling formula}} for details.
		+	:Seems your memory just dropped that log. [[Special:Contributions/198.41.242.245\|198.41.242.245]] 08:57, 27 June 2016 (UTC)

@@ Line 61: / Line 61: @@
 </pre>
 :::If what you said was true, modern computer science would collapse. Even if you don't believe me, you have to concede that the mere fact you ''can'' sort 65536 things before the heat death of the universe is proof that you did the math wrong. [[Special:Contributions/173.245.54.28|173.245.54.28]] 03:42, 19 November 2015 (UTC)
-::1) I think you might be confused on how math works. n! refers to factorial (1*2*3...n) while n log n is the n multiply logarithm n.
+::1) I think you might be confused on how math works. n! refers to factorial (1*2*3...n). n log n is n multiplied by the logarithm of n.
 ::2) Didn't read all of the rambling, but it seems like you believe a list can only be sorted by brute-force, going over each item and comparing it to the rest of the list. This would in fact be n!. Most sorting algorithms do not use the brute force method since humans are built to recognize patterns and come up with algorithms regarding those patterns. [[User:Flewk|Flewk]] ([[User talk:Flewk|talk]]) 01:13, 28 December 2015 (UTC)

← Older revision		Revision as of 01:13, 28 December 2015
Line 61:		Line 61:
	</pre>		</pre>
	:::If what you said was true, modern computer science would collapse. Even if you don't believe me, you have to concede that the mere fact you ''can'' sort 65536 things before the heat death of the universe is proof that you did the math wrong. [[Special:Contributions/173.245.54.28\|173.245.54.28]] 03:42, 19 November 2015 (UTC)		:::If what you said was true, modern computer science would collapse. Even if you don't believe me, you have to concede that the mere fact you ''can'' sort 65536 things before the heat death of the universe is proof that you did the math wrong. [[Special:Contributions/173.245.54.28\|173.245.54.28]] 03:42, 19 November 2015 (UTC)
		+	::I think you might be confused on how math works. n! refers to factorial (123...n) while n log n is the n multiply logarithm n. [[User:Flewk\|Flewk]] ([[User talk:Flewk\|talk]]) 01:13, 28 December 2015 (UTC)

@@ Line 32: / Line 32: @@
 function merge_sort(arr) {
-	if(arr.length == 1) {return arr;}
+	if(arr.length <= 1) {return arr;}
 	var left = merge_sort(arr.slice(0, Math.floor(arr.length / 2)));

@@ Line 28: / Line 28: @@
 :::> ''any comparison sort must distinguish between O(n!) lists, and therefore can never do that with less than O(n! -1)=O(n!) comparisons.''
 :::This suggests to me that you've never written a comparison sort. Here's merge sort in JS:
-<pre style="margin: 6em;">
+<pre style="margin: 0 6em;">
 window.comparisons = 0;