程序运行的时间复杂度是指程序运行的时间还是指程序运行的次数或者指别的什么？敬请专家赐教！！！

Question

程序运行的时间复杂度是指程序运行的时间还是指程序运行的次数或者指别的什么？

Answer 1

时间复杂度是算法时间效率的一个度量标准。一般而言，时间效率可以用算法中执行某些基本操作的次数来表示。比如对n个整数排序的选择排序：
    public void selectSort(int[] arr){ 
        for(int i=0;i <arr.length;i++){ 
            int temp=0; 
            int min=i;          
            for(int j=1+i;j <arr.length;j++){  
                if(arr[j] <arr[min]) { 
                    min=j; 
                }
            }
            temp=arr[min];
            arr[min]=arr[i];
            arr[i]=min;
        }以比较元素为基本操作，来计算执行基本操作的次数,n为整数的个数，也叫问题的规模:
第一趟选择最小的元素，执行的比较次数是n-1，
第二趟选择最小的元素，执行的比较次数是n-2.

第n-1趟选择最小的元素，执行的比较次数是1.整个算法执行比较的次数是：1+2+...+n-1=n(n-1)/2=n^2/2-n/2
所以也可以说选择排序算法的时间效率是n^2/2-n/2所谓的时间复杂度就是指不带系数的最高次，记为O(n^2).有研究表明，当n非常大时，最高次是影响整个算法时间效率的最主要因素。所以要用O(n^2)来表示选择排序的时间复杂度。