o (1)의 배열에 링크 목록을 복사 할 수 있습니까 (둘 다 크기가 n입니까?)?

Question

O (1)의 배열에 링크 목록을 복사 할 수 있습니까 (둘 다 크기가 n입니까?)?

즉, 링크 목록의 요소와 배열의 크기는 동일하지 않습니다.

Answer 1

하나의 짧은 대답. 번호

질문이 불완전하고 일부 제약 조건이 누락되었지만 답은 분명히 아니오입니다.

Answer 2

아니요 : n 요소를 복사해야하는 경우 n 작업이 필요합니다. O (n)에서 목록을 탐색하고 배열의 각 요소를 O (1)에 삽입 할 수 있습니다. 가변 개수의 요소를 처리하는 일정한 시간을 기대할 수는 없습니다.

Answer 3

아니요 ... 복사 작업 자체가 O (1) 연산 인 동안 N 번 발생하므로 전체 연산의 복잡도는 O (N)이됩니다.

Answer 4

당신이 Linked List 및 Array을 고려 무엇을 조금 다시 정의하지 않는 한 제

. 엄밀히 말하면 전제 조건을 만들어야합니다.

당신이 가지고있는 경우 : 불변의 구조

그런 다음 모든 Linked List는 Array (당신이 요소 n에 있다면, 그것은 (1) n-1 및 n+1에 갈 O는, 그래서 "읽기"일부가 될 수있다 동급 일 것입니다.) 당신이 "용기"에서 "포함"을 분할하는 경우이 시점에서, 당신은 (AN Array, 또는 Linked List에 Array, 또는 Array 또는 모든 O의 Linked List에 Linked List에 Linked List 1을 Array을 복사 할 수). (C에서 #) I 의미 포함 된 컨테이너에서 분할에서 : 데이터 소스도를 허용하는 생성자, 복사 생성자

struct MyArray 
{ 
    private int[] baseArray; 

    public int this[int index] 
    { 
     get 
     { 
      return baseArray[index]; 
     } 
    } 
} 

struct MyList 
{ 
    private int[] baseArray; 

    public Tuple<int, int> First() 
    { 
     return new Tuple<int, int>(0, baseArray[0]); 
    } 

    public Tuple<int, int> Next(Tuple<int, int> current) 
    { 
     return new Tuple<int, int>(current.Item1 + 1, baseArray(current.Item1 + 1)); 
    } 
} 

를 단순히 복사 baseArray에 대한 참조 (이 될 O (1) 때문에 우리는 단지 참고 문헌 만 복사하고있다.) 그리고 다른 모든 필요한 방법들.

(너무 많은이 답변을 downvote하지 마십시오. 그것은 더는 도발 및/또는 상자 밖으로 생각입니다)

(나는 그들이 매우 사실을 지적 C 번호를 struct의를 사용하고 있습니다 light objects. 실제 "고기"는 baseArray의 "내부"입니다.이 구조체는 참조와 메소드를 약간 넘는 것입니다.