일부 작업이있는 이중 링크 목록

Question

숫자 요소가 포함 된 이중 연결 목록 Q의 경우 첫 번째 요소와 마지막 요소에 대한 포인터가 있으므로 두 작업을 정의합니다.

Delete (k): delete k first elements from Q. 

Append (c), check the last element from `Q`, if this value bigger than c, delete this elements and repeat it again until the last element is lower or equal to `c` (or empty `Q`), then insert c as last elements of Q`.` 

우리는 논문 작업의 모든 비용의 합이 2n에 가까운, 빈리스트 Q에 n 번 임의의 순서로이 두 작업의 순서를 반복합니다. 내 강사가 2n에 도달하는 이유는 무엇입니까? 어떤 힌트 또는 아이디어도 감사합니다. 우리가 논문 조작의 모든 비용의 빈 목록 Q 합에 n 개의 시간에 대한 임의의 순서로 이러한 작업을 반복하면 우리가 목록을 알고 있기 때문에 그것은 실제로 O(n) 될 것

Answer 1

때 우리 "빈리스트 Q에 n 시간에 대한 임의의 순서로 반복 Delete 및 Append"Append가 호출 n 시간; 따라서 정확히 n 목록 요소 삽입이 수행됩니다.

목록은 처음에는 비어 있으므로 n 개 이상의 요소를 포함하지 않습니다. 그러므로 많아야 n 목록 요소 삭제는 Delete과 Append의 조합으로 수행됩니다.

Delete 및 Append (이 포함 Append 판독)의 각각에 따라서 루프의 총 개수가 2 개 이하 n 없다.

따라서 전체적으로 프로그램의 섹션은 2 개 이상 실행되지 않습니다 (목록 요소 삽입, 목록 요소 삭제 및 목록 요소 액세스에 공통적 인 코드를 별도로 계산). 우리는 n 목록 요소 삽입을 가지고 n 목록 요소 읽기 (일 반환 빈), n emptyness 검사, n-1 요소 비교 : k은 항상 0이며, c 비 감소 (항상 포함 0) 때

비용은 최소화 삭제되지 않습니다. 따라서 비용은 매개 변수에 따라 크게 달라집니다.

참고 : 따라서, 심지어 잘못된 잘못 정의되어 있지 "논문 조작의 모든 비용 합계 2 n에 가깝습니다." 더 나쁜 것은 목록 요소 삭제가 일부 불운 (예 : 코드 캐시 누락, 디버그 코드 ..)에 의해 나머지보다 훨씬 느린 경우 매개 변수에 따라 코드 지속 시간이 큰 요인 (2보다 훨씬 높음)에 따라 달라질 수 있습니다. . 따라서 실행 시간은 임의의 의미에 대해 이 아니며 항상 " 약 2 n"이 아닙니다.

업데이트 : comment, 우리는 그 목록 요소 삽입을 이야기하고 삭제 같은 비용 1.이 n 목록 요소의 삽입이 있습니다, 그리고 n 0 사이 목록 요소 삭제. 그러므로 우리가 다른 비용 (메모리 할당 비용이 지배적이라는 것이 합리적이다)을 무시한다면, 총 비용은 매개 변수에 따라 약 n ~ 약 2 n입니다. 또한 대부분의 경우 k> = 1을 포함하여 많은 매개 변수에 대해 거의 n 목록 요소 삭제가 있으므로 객관식 질문 에서처럼 (a)와 같은 최상의 추측을 주장하면 비용은 약 2 n입니다. n + k (b) n (c) 2 n (d) 3 n이 유일한 옵션입니다.

Answer 2

를 내지 2N 가까운 Q 비었다.

DoStuff(list Q, int n): 
    for(int i = 0; i < n; i++) 
     Q.Delete(k) //O(k) 
     Q.Append(c) //O(sizeof(Q)) 
     //or 
     //Q.Append(c) //O(sizeof(Q)) 
     //Q.Delete(k) //O(k) 

여기에서 n은 반복 횟수입니다.

이제 목록이 비어 있지 않으면, O(n*(sizeof(Q)+k))이됩니다. 그에 대한 설명은 다음과 같습니다 :

이 k 다음 우리는 삭제 n 개의 요소 것, Q의 크기입니다 Delete (k)에 대한 최악의 시나리오는 Q에서 K 첫번째 요소를 삭제하는 것입니다 말해. 그러나 항상 k 요소 만 삭제하기 때문에 O(k)이라고 말하는 것이 정확합니다.

Append (c)의 경우 악의적 인 시나리오는 Q의 모든 요소가 c보다 큽니다. 이것은 테일 노드에서 시작하여 모든 노드를 Q에서 삭제합니다. 중 하나를 위해

Delete(k) //O(k) 
Append(c) //O(sizeof(Q)) 

또는

Append(c) //O(sizeof(Q)) 
Delete(k) //O(k) 

그냥이 두 명령에 대한 최악의 경우에있을 것이라고는 O(sizeof(Q)+k)입니다. 이제 우리는 우리가이 n 반복 할 필요가 알고, 그래서 우리는 마침내 교수가 한 말에 대해서는 O(n*(sizeof(Q)+k))

을 얻을, 나는 이 상상할 수있는 유일한 이유 당신의 교수가 호출되는 2 기능이 있기 때문에 2n는 말했다 n 번. 따라서 2n.