정렬 된 목록에 건물/삽입

Question

여기에 문제가 있습니다. 정렬 된 목록에 삽입 할 N 개의 난수 집합이 있습니다 (가장 작은 것부터 가장 큰 것까지). 전체 목록에 대한 최악의 경우의 점근 시간 성능은 어떻게됩니까?

몇 가지 언어로 된 코드로 정렬 된 목록을 삽입하는 방법을 알고 있습니다. 두 가지 다른 방법이 있습니다. 프로그램에서 한 항목 더 배열에 아직 공간이 있는지 확인합니다. 그런 다음 목록에 항목을 삽입하려면 삽입 할 항목보다 큰 모든 항목이 for 루프를 통해 오른쪽으로 이동됩니다. 그런 다음 삽입 할 항목에 대한 포인터가 적절한 배열 위치에 기록되어 있습니다. C++에서 :

void SortedListAsArray::Insert (Object& object) 
{ 
    if (count == array.Length()) 
     throw domain_error ("list is full"); 
    unsigned int i = count; 
    while (i > 0 && *array [i - 1U] > object) 
    { 
     array[i] = array [i - 1U]; 
     --i; 
    } 
    array[i] = &object; 
    ++count; 
} 

내가 생각하는 이것은 O (n)의 시간. 저를 혼란스럽게하는 것은 전체 목록 부분을 전체적으로 "구축"하는 것입니다. 그 숫자를 주어진 처음부터 목록을 만들고 삽입 한 다음, 이미 정렬 된 목록에 숫자 세트를 삽입하는 것이 확실한지는 모르겠습니다. 너희들은 그것이 무엇을 의미한다고 생각하니 어느쪽으로 든 내 실행 시간을 바꿀 것인가? 감사!

Answer 1

알아 냈어. 2 개의 for 루프를 사용하면 다른 방법으로 (그리고 더 쉽게) O (n^2)가됩니다. 이미 정렬 된 목록이 있다고 가정하고 삽입 유형을 사용하여 숫자를 삽입합니다.