LinkedList와 LinkedList의 타당성정렬된 배열과 정렬된 배열정렬되지 않은 데이터?

StackOverflow https://stackoverflow.com/questions/276278

  •  07-07-2019
  •  | 
  •  

문제

LinkedList와 배열을 비교하는 동시에 정렬된 데이터와 정렬되지 않은 데이터의 차이점도 비교

  • 첨가
  • 풀이
  • 검색 중
  • 정렬
  • 전체 속도
  • 전체 메모리 사용량

실제 질문

정렬되지 않은 데이터 세트를 배열이 아닌 연결된 목록으로 구현하는 가능성에 대해 논의하세요.삽입, 제거, 검색, 컴퓨터 메모리 및 응용 프로그램 속도 측면에서 장단점은 무엇입니까?

정렬된 데이터 세트를 배열이 아닌 연결된 목록으로 구현하는 가능성에 대해 논의하세요.삽입, 제거, 검색, 컴퓨터 메모리 및 응용 프로그램 속도 측면에서 장단점은 무엇입니까?

이전 질문에 대한 답변을 바탕으로 응용 프로그램에서 연결 목록을 사용할 때의 비용과 이점을 요약하십시오.

내 답변/입력:

LinkedList는 새 노드가 추가될 때마다 메모리를 할당해야 하며, 많은 노드를 추가할 때 유용하며 크기는 계속 변경되지만 일반적으로 요소를 거의 추가할 때 속도가 느려집니다.

프로그램 실행 시작 시 할당된 메모리 배열, 목록 크기 조정 속도 느림(크기 조정이 필요한 경우 많은 요소 추가 속도 느림)

인덱싱으로 인해 배열에서 검색이 더 빠릅니다.

포인터로 인해 LinkedList에서 더 빠르게 추가/제거

도움이 되었습니까?

해결책

분류되지 않은 대 정렬. 하나도 할게요, 그럼 정말 숙제를해야합니다

StackoverFlow 마크 업에는 실제로 테이블이 필요합니다. 당신은 분류되지 않은/배열, 분류/배열, 미묘한/링크리스트, 정렬/링크리스트에 대한 조작이 얼마나 "비싸다"고 말하고 싶습니다.

마지막 요점 : "응용 프로그램의 속도"는 개별 작업 속도 이상을 고려하는 힌트입니다. 

* Adding

분류되지 않은 : 배열 추가는 O (1) 크기를 조정하지 않는 한 O (1)입니다. 끝에 추가하십시오. 오버 헤드를 최소화하는 크기 조정 전략에 대해 논의 할 수 있습니다 (힌트 : 크기를 하나씩 증가시키지 마십시오).

정렬 : 배열 추가는 O (n)입니다 - 추가 할 장소를 찾는 것은 O (log (n))이지만 새로운 것을 위해 ROMM을 만들려면 (평균적으로) 요소의 절반을 움직여야합니다.

Unsorted : 링크 된 목록은 O (1)입니다. 목록의 시작 또는 끝에 추가하십시오.

정렬 : 링크 된 목록은 O (n)입니다. O (1)에 요소를 다시 추가 할 수는 있지만 평균적으로 목록의 절반을 스캔하려면 장소를 찾아야합니다.

그래서 나머지는 당신에게 넘어갑니다. 답을 게시하면 우리는 그것을 비판하지만, (아마도) 비싼 교육에서 최대한 활용하려면, 당신은 정말로 이것에 대해 약간의 일을해야합니다 :)

* Removing
* Retrieving
* Sorting
* Overall speed
* Overall memory usage

다른 팁

이것이 어떤 클래스인지 확실하지 않지만 CS 프로그램의 경우 "느리게"보다 더 잘해야하고 "빠른"것보다 더 잘해야합니다. 수술 수가 필요하다는 점에서 그것을 정량화하십시오. 그러한 정량화에 일반적으로 사용되는 기계에 익숙해야합니다.

Here is a C++ code that illustrates that sorting the data miraculously makes the code faster than the unsorted version. Let’s try out a sample C++ program to understand the problem statement better.

// 프로세싱을 보여주는 CPP 프로그램 // 분류되지 않은 배열의 시간

#include <iostream>
#include <algorithm>
#include <ctime>
using namespace std;

const int N = 100001;

int main()
{
    int arr[N];

    // Assign random values to array
    for (int i=0; i<N; i++)
        arr[i] = rand()%N;

    // for loop for unsorted array
    int count = 0;
    double start = clock();
    for (int i=0; i<N; i++)
        if (arr[i] < N/2)
            count++;

    double end = clock();
    cout << "Time for unsorted array :: "
         << ((end - start)/CLOCKS_PER_SEC)
         << endl;
    sort(arr, arr+N);

    // for loop for sorted array
    count = 0;
    start = clock();

    for (int i=0; i<N; i++)
        if (arr[i] < N/2)
            count++;

    end = clock();
    cout << "Time for sorted array :: "
         << ((end - start)/CLOCKS_PER_SEC)
         << endl;

    return 0;
}

// 코드의 출력

Output :

Execution 1:
Time for an unsorted array: 0.00108
Time for a sorted array: 0.00053

Execution 2:
Time for an unsorted array: 0.001101
Time for a sorted array: 0.000593

Execution 3:
Time for an unsorted array: 0.0011
Time for a sorted array: 0.000418
Observe that time taken for processing a sorted array is less as compared to an unsorted array. The reason for this optimization for a sorted array is branch prediction.

@폴:감사해요

  • 풀이

정렬되지 않은 것과 정렬된 것:배열 제거는 O(n)입니다. '구멍'을 채우기 위해 모든 요소를 ​​이동해야 합니다.

정렬되지 않은 것과 정렬된 것:연결된 목록은 O(1)입니다. 필요에 따라 포인터를 변경합니다.

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top