程序 = 數(shù)據(jù)結(jié)構(gòu) + 算法
數(shù)據(jù)
數(shù)據(jù): 程序的操作對(duì)象,用于描述客觀事物.
數(shù)據(jù)的特點(diǎn): 1?? 可以輸入到計(jì)算機(jī) 2?? 可以被計(jì)算機(jī)處理
數(shù)據(jù)項(xiàng): 一個(gè)數(shù)據(jù)元素由若干數(shù)據(jù)項(xiàng)組成
數(shù)據(jù)元素: 組成數(shù)據(jù)的對(duì)象的基本單位
數(shù)據(jù)對(duì)象: 性質(zhì)相同的數(shù)據(jù)元素的集合(類似于數(shù)組)
結(jié)構(gòu): 數(shù)據(jù)元素之間不是獨(dú)立的,存在特定的關(guān)系.這些關(guān)系即是結(jié)構(gòu);
數(shù)據(jù)結(jié)構(gòu):指的數(shù)據(jù)對(duì)象中的數(shù)據(jù)元素之間的關(guān)系
#include <stdio.h>
//聲明一個(gè)結(jié)構(gòu)體類型
struct Teacher{ //一種數(shù)據(jù)結(jié)構(gòu)
char *name; //數(shù)據(jù)項(xiàng)--名字
char *title; //數(shù)據(jù)項(xiàng)--職稱
int age; //數(shù)據(jù)項(xiàng)--年齡
};
int main(int argc, const char * argv[]) {
struct Teacher t1; //數(shù)據(jù)元素;
struct Teacher tArray[10]; //數(shù)據(jù)對(duì)象;
t1.age = 18; //數(shù)據(jù)項(xiàng)
t1.name = "CC"; //數(shù)據(jù)項(xiàng)
t1.title = "講師"; //數(shù)據(jù)項(xiàng)
printf("老師姓名:%s\n",t1.name);
printf("老師年齡:%d\n",t1.age);
printf("老師職稱:%s\n",t1.title);
return 0;
}
數(shù)據(jù)
數(shù)據(jù)結(jié)構(gòu)
數(shù)據(jù)與數(shù)據(jù)直接的邏輯關(guān)系
-
[Set]
集合結(jié)構(gòu) -
[Array, String, Dictionary]
線性結(jié)構(gòu) -
[二叉樹(shù)] 1對(duì)多
樹(shù)形結(jié)構(gòu) -
多對(duì)多
圖形結(jié)構(gòu)
- 物理結(jié)構(gòu)
-
數(shù)組
樹(shù)形存儲(chǔ) -
鏈表
鏈?zhǔn)酱鎯?chǔ)
算法比較
算法：算法是解決特定問(wèn)題步驟的描述牲距， 在計(jì)算機(jī)中表現(xiàn)為指令的有限序列，并且每一個(gè)指令表示一個(gè)或者多個(gè)操作。
算法的特性
- 輸入輸出
- 有窮性
- 確定性
- 可行性
算法要求
- 正確性
- 可讀性
- 健壯性
- 時(shí)間效率和存儲(chǔ)量低
時(shí)間復(fù)雜度
大O表示法
- 用常數(shù)1取代運(yùn)行時(shí)間中所有常數(shù) 3->1 O(1)
- 在修改運(yùn)行次數(shù)函數(shù)中,只保留最高階項(xiàng) n3+2n2+5 -> O(n^3)
- 如果在最高階存在且不等于1,則去除這個(gè)項(xiàng)目相乘的常數(shù) 2n^3 -> n^3
/*
時(shí)間復(fù)雜度術(shù)語(yǔ):
1. 常數(shù)階
2. 線性階
3. 平方階
4. 對(duì)數(shù)階
5. 立方階
6. nlog階
7. 指數(shù)階(不考慮) O(2^n)或者O(n!) 除非是非常小的n,否則會(huì)造成噩夢(mèng)般的時(shí)間消耗. 這是一種不切實(shí)際的算法時(shí)間復(fù)雜度. 一般不考慮!
*/
/* 1. 常數(shù)階時(shí)間復(fù)雜度計(jì)算 O(1) */
//1+1+1 = 3 O(1)
void testSum1(int n){
int sum = 0; //執(zhí)行1次
sum = (1+n)*n/2; //執(zhí)行1次
printf("testSum1:%d\n",sum);//執(zhí)行1次
}
//1+1+1+1+1+1+1 = 7 O(1)
void testSum2(int n){
int sum = 0; //執(zhí)行1次
sum = (1+n)*n/2; //執(zhí)行1次
sum = (1+n)*n/2; //執(zhí)行1次
sum = (1+n)*n/2; //執(zhí)行1次
sum = (1+n)*n/2; //執(zhí)行1次
sum = (1+n)*n/2; //執(zhí)行1次
printf("testSum2:%d\n",sum);//執(zhí)行1次
}
//x=x+1; 執(zhí)行1次 O(1)
void add(int x){
x = x+1;
}
/*2.線性階時(shí)間復(fù)雜度*/
//x=x+1; 執(zhí)行n次 O(n)
void add2(int x,int n){
for (int i = 0; i < n; i++) {
x = x+1;
}
}
//1+(n+1)+n+1 = 3+2n -> O(n)
void testSum3(int n){
int i,sum = 0; //執(zhí)行1次
for (i = 1; i <= n; i++) { //執(zhí)行n+1次
sum += i; //執(zhí)行n次
}
printf("testSum3:%d\n",sum); //執(zhí)行1次
}
/*3.對(duì)數(shù)階*/
/*2的x次方等于n x = log2n ->O(logn)*/
void testA(int n){
int count = 1; //執(zhí)行1次
//n = 10
while (count < n) {
count = count * 2;
}
}
/*4.平方階*/
//x=x+1; 執(zhí)行n*n次 ->O(n^2)
void add3(int x,int n){
for (int i = 0; i< n; i++) {
for (int j = 0; j < n ; j++) {
x=x+1;
}
}
}
//n+(n-1)+(n-2)+...+1 = n(n-1)/2 = n^2/2 + n/2 = O(n^2)
//sn = n(a1+an)/2
void testSum4(int n){
int sum = 0;
for(int i = 0; i < n;i++)
for (int j = i; j < n; j++) {
sum += j;
}
printf("textSum4:%d",sum);
}
//1+(n+1)+n(n+1)+n^2+n^2 = 2+3n^2+2n -> O(n^2)
void testSum5(int n){
int i,j,x=0,sum = 0; //執(zhí)行1次
for (i = 1; i <= n; i++) { //執(zhí)行n+1次
for (j = 1; j <= n; j++) { //執(zhí)行n(n+1)
x++; //執(zhí)行n*n次
sum = sum + x; //執(zhí)行n*n次
}
}
printf("testSum5:%d\n",sum);
}
/*5.立方階*/
void testB(int n){
int sum = 1; //執(zhí)行1次
for (int i = 0; i < n; i++) { //執(zhí)行n次
for (int j = 0 ; j < n; j++) { //執(zhí)行n*n次
for (int k = 0; k < n; k++) {//執(zhí)行n*n*n次
sum = sum * 2; //執(zhí)行n*n*n次 O(n^3)
}
}
}
}
int main(int argc, const char * argv[]) {
testSum1(100);
testSum2(100);
testSum3(100);
return 0;
}
- 按最高階算
常見(jiàn)時(shí)間復(fù)雜度計(jì)算
空間復(fù)雜度
/*
程序空間計(jì)算因素:
1. 寄存本身的指令
2. 常數(shù)
3. 變量
4. 輸入
5. 對(duì)數(shù)據(jù)進(jìn)行操作的輔助空間
在考量算法的空間復(fù)雜度,主要考慮算法執(zhí)行時(shí)所需要的輔助空間.
空間復(fù)雜度計(jì)算:
問(wèn)題: 數(shù)組逆序,將一維數(shù)組a中的n個(gè)數(shù)逆序存放在原數(shù)組中.
*/
#include <stdio.h>
int main(int argc, const char * argv[]) {
// insert code here...
printf("Hello, World!\n");
int n = 5;
int a[10] = {1,2,3,4,5,6,7,8,9,10};
//算法實(shí)現(xiàn)(1)
int temp;
for(int i = 0; i < n/2 ; i++){
temp = a[i];
a[i] = a[n-i-1];
a[n-i-1] = temp;
}
for(int i = 0;i < 10;i++)
{
printf("%d\n",a[i]);
}
//算法實(shí)現(xiàn)(2)
int b[10] = {0};
for(int i = 0; i < n;i++){
b[i] = a[n-i-1];
}
for(int i = 0; i < n; i++){
a[i] = b[i];
}
for(int i = 0;i < 10;i++)
{
printf("%d\n",a[i]);
}
return 0;
}
