Homework help?

2017-02-09 4:16 am
The first time you run algorithm A on a dataset of n elements; it is faster than
algorithm B. The second time you run algorithm A on a dataset of n elements; it is slower thanalgorithm B.
Explain how this is possible. Give an example for algorithm A and algorithm B

回答 (4)

2017-02-09 4:21 am
✔ 最佳答案
Algorithm A and B do not have the same internal workings.

Typically different types sorts would an example

Bubble sort has worst-case and average complexity both О(n2), where n is the number of items being sorted. There exist many sorting algorithms with substantially better worst-case or average complexity of O(n log n). Even other О(n2) sorting algorithms, such as insertion sort, tend to have better performance than bubble sort. Therefore, bubble sort is not a practical sorting algorithm when n is large.

The only significant advantage that bubble sort has over most other implementations, even quicksort, but not insertion sort, is that the ability to detect that the list is sorted efficiently is built into the algorithm. When the list is already sorted (best-case), the complexity of bubble sort is only O(n). By contrast, most other algorithms, even those with better average-case complexity, perform their entire sorting process on the set and thus are more complex. However, not only does insertion sort have this mechanism too, but it also performs better on a list that is substantially sorted (having a small number of inversions).

Bubble sort should be avoided in the case of large collections. It will not be efficient in the case of a reverse-ordered collection.
2017-02-09 7:36 am
It sounds like a cache usage symptom. The first time through the CPU cache will have to be loaded with both code and data. Depending upon the size of the cache and the usage profile for the code and data, for one algorithm the cache may take longer on its initial code load and less time with the data. The other algorithm may have a fast code load but be slower in processing the data.

I hope this helps.
2017-02-09 7:05 am
Consider sorting algorithms A & B the time necessary could depend upon the ordering of the data.

[email protected]
2017-02-09 4:17 am
K


收錄日期: 2021-04-24 00:15:39
原文連結 [永久失效]:
https://hk.answers.yahoo.com/question/index?qid=20170208201641AA7X5aq

檢視 Wayback Machine 備份