코드 - 우수한 라이브러리

에 대한 복잡도 분석 결과로 오늘 수정 된 디렉토리 및 하위 디렉토리의 파일을 나열하는 Java 코드를 작성했습니다. 시간과 공간의 복잡성을 이해하는 데 약간의 도움이 필요합니다.코드

코드 :

공용 클래스 FileInDir {

File[] files = null; 
Date d = new Date(); 
long mill; 

public void listTodayFiles(String path) { 
    File dir = new File(path); 
    files = dir.listFiles(); 

    for(File file : files){ 
     mill = file.lastModified(); 
     Date f = new Date(mill); 

     if(f.getDate() == d.getDate()){ 
      if(file.isFile()) 
       System.out.println("FILE: " + file.getName() + " WAS LAST MODIFIED ON: " + f); 
      else if(file.isDirectory()) 
       listTodayFiles(file.getAbsolutePath()); 
     } 
    } 
}

}

그래서 내가 이해에서

는, 배열에있는 모든 파일을 저장하는 O 소요 (n)의 시간 , 루프 O (n) 시간이 걸립니다. 재귀 호출의 복잡성에 대해서는 확신 할 수 없습니다. If 문이 시간이나 공간의 복잡성에서 중요한 역할을하는지 확신 할 수 없습니다. 또한 각 요소 (파일)를 저장해야하기 때문에 공간 복잡성은 O (n)이됩니다.

감사합니다 : D

출처

2014-12-23 Mohamed Qulateen

[빅 오, 당신은 어떻게 계산합니까/대략입니까?] (http://stackoverflow.com/questions/3255/big-o-how-do-you-calculate-approximate-it) – Suma

귀하의 복잡성은 n을위한 선택에 따라 달라집니다. n이 파일 수이면 각 파일을 한 번 방문하기 때문에 복잡성은 O (n)입니다.

출처

2014-12-23 10:41:44 wvdz

@popovitsj에서 정의한대로 시간 복잡도가 정확합니다.

재귀 호출로 인해 각 파일 객체를 스택에 저장해야하므로 공간 복잡성 또한 O (n)입니다.

출처

2014-12-23 10:44:57

여러 레벨의 디렉토리가 있습니다. 다음 그것은 또한 동일합니까 ?? – Prashant

내 디렉터리가 재귀 호출을 수행 할 필요가 없다는 의미의 파일로만 구성되는 경우 공간 복잡성에 영향을 줍니까? 또한 하위 디렉토리에있는 각 파일을 방문해야하기 때문에 하위 디렉토리가 시간 복잡성에 영향을 미칩니다. –

@Prashant 그것은 다중 레벨의 디렉토리가 있거나 "n"개의 파일과 동일한 디렉토리라고 말하는 최악의 시나리오입니다. 공간의 복잡성은 많은 파일 객체를 생성하기 때문에 항상 동일하게 유지됩니다. –

코드

답변

관련 문제