내 LinkedList에서 head_pop()과 append()는 같은 시간이 걸립니까?

Question

LinkList의 끝 부분에 요소를 추가하는 것보다 빠르게 LinkList의 head 요소를 삭제하는지 테스트하고 싶습니다.

class LNode: 
    def __init__(self,elem,next_=None): 
     self.elem=elem 
     self.next=next_ 

class LinkList: 
    def __init__(self): 
     self.__head=None 

    #delete head element 
    def head_pop(self): 
     if self.__head is None: 
      raise LinkedListUnderflow("in pop") 
     e=self.__head.elem 
     self.__head=self.__head.next 
     return e 

    #add an element at end 
    def append(self,elem): 
     if self.__head is None: 
      self.__head=LNode(elem) 
      return 
     p=self.__head 
     while p.next is not None: 
      p=p.next 
     p.next=LNode(elem) 

import time 

#test time 
def timetest(f): 
    start=time.clock() 
    for a in range(0,1000000): 
     f 
    end=time.clock() 
    print("times:"+str(end-start)) 

후, 나는이 시도 :

llist=LinkList() 

def append(): 
    llist.append(666) 

def head_pop(): 
    llist.head_pop() 

timetest(append()) 
timetest(head_pop()) 

출력 : 당신이 볼 수 있듯이

times:0.029582597002445254 
times:0.03032071299821837 

, 그들은 비용을 동시에

이 내 LinkList의 주요 코드입니다.

하지만 O (n) : O (1)이어야한다고 생각합니다.

Answer 1

append()의 결과를 시간 테스트 기능에 전달하는 반면 기능 자체는 전달하려고합니다. 당신이 볼 수 있듯이

timetest(append) 
timetest(head_pop) 

, 우리가 테스트 기능에 전달되고 있습니다

def timetest(f): 
    start=time.clock() 
    for a in range(0,1000000): 
     f() # <- note the() here 
    end=time.clock() 
    print("times:"+str(end-start)) 

그런 다음 시험이 사용

는 f 함수를 호출 할 시간 테스트를 변경

함수의 결과 대신에 호출 할 수 있습니다. (한 번 호출됩니다!)